*Height Balanced Binary tree*

- A binary search tree is said to be a height balanced binary search if all its nodes have a balance factor of 1,0,or -1

**Balance factor of a binary tree**

- The balance factor of a binary tree is defined as
- bf=height of the left sub-tree(h
_{l})-height of right sub-tree(h_{r}) - So, in a height balanced binary search tree all the nodes have a balance factor.
- |bf|=|h
_{l}-h_{r}|≤ 1

**Example:1**

Height balanced tree

__Solution:__

Balance factor

⇒|6|=|3-2|=1

⇒|2|=|1-2|=1

⇒|1|=|0-0|=0

⇒|4|=|1-0|=1

⇒|3|=|0-0|=0

⇒|8|=|1-0|=1

⇒|7|=|0-0|=0

**Example 2** Height balanced tree

*Solution*:

Here, you will get to know how to find balance factor.

⇒|6|=|3-1|=2

⇒|2|=|1-2|=1

⇒|1|=|0-0|=0

⇒|4|=|1-1|=0

⇒|3|=|0-0|=0

⇒|5|=|0-0|=0

⇒|8|=|0-0|=0

- The basic objective of the height balanced binary search tree is to perform searching,insertion and deletion operation efficiently.

*AVL*

- Height balanced trees, also called as AVL trees because of an unbalanced tree can be converted into a balanced tree by using a method devised by two Russian Mathematicians ,
**G.M.Adelson-Velskii and** **E.M.Landis **and the method is named as AVL rotation in their honour. **Node in a height balanced tree**

The node structure to maintain a height balanced tree is

*B trees*

**Indexing**:The purpose of the indexing is to accelerate the search procedure- Binary search tree is a
__2-way__ search tree and uses the concept of tree indexing,where each node contains a key value,pointers to the left sub-tree and right sub-tree. - Binary search tree is a 2-way search tree(m=2)

**Definition:**

- An m-way(m≥ 2) search tree T is a tree in which all the nodes are of degree less than or equal to m.
- Each node in the tree contains the following attributes:

K_{i}(1≤i≤n) are the key values.

P_{i}(0≤i≤n) are printers to the subtree of T.

K_{i}<K_{i+1} , 1≤i<n

- All the key values in the sub-tree pointed by P
_{i} are less than the key K_{i+1} , 0≤i<n - All the key values in the sub-tree pointed by P
_{n} is greater than K_{n.} - All the sub-trees pointed by P
_{i}(0≤i≤n) are also the m-way search tree.

__Types of m-way search tree:__

- There are two types of m-way search tree:
- B tree
- B+ tree

**B tree**:

If the m-way search tree is height balanced then,it is called as B tree or B tree indexing.

**Definition:**

A B tree T of order m is an m-way search tree,that is either it is empty or it satisfies the following properties:

- The root node has atleast 2-children.
- All the nodes other than the root node have atleast [m/2] children.
- All failure nodes are at the same levels.

**Failure node**:

A failure node represents a node which can be reached during a search only if the value ,say X ,being searched for is not in the tree.

- For convinience,these empty sub-trees are replaced by hypothetical nodes are called failure nodes.

**Example**: A B tree of order 3

__Operations on B tree__

- Searching
- Insertion
- Deletion

*B+ tree*

- A B+ tree is an N-array type with a variable but often large number of children per node.
- A B+ tree consists of a root,internal node and leaves.The root may be either a leaf on a node with two or more children.

*A B+ tree maintains the following invariants*

- Every node has one more references than it has keys.
- All the leaves are at the same distance from the root.
- For every non-leaf node N with K being the number of keys in N :all the keys in the first child's sub-tree are less than N's first key; and all the keys in the i
^{th} child's sub-tree(2=i=K)are between the (i-1)^{th} key of n and the i^{th} key of n. - The root has atleast two children.
- Every non-leaf ,non-root node has atleast floor(d/2) children.
- Each leaf contains atleast floor(d/2) keys.
- Every key from the table appears in the least,in left to right sorted order.

**Example**:

Here is a small tree using 4 as our value for d.

*Red Black tree*

- Red-black tree is used to keep a tree balanced.
- It is a binary search tree.
**Ruddf Bayer** and **E.M.MCGreight** proposed the concept of a red-black tree as a special case of B-tree.

**Definition:**

- A red-black tree is a binary search tree that satisfies the following properties:

**Color property:**

- Every node is either red or black.

**Root property**:

- The root is always colored with black.

**External property:**

- Every external node is black.

**Internal property:**

- If a node is red then,both its children are black.

**Depth property:**

For each node,all paths from that node to descendant external nodes contain the same number of black nodes.

**Black depth:**

- The number of black ancestors from an external node to any node is defined as the black depth.

**Example**:

__Height of the red-black tree:__

A red-black tree with n internal nodes has at most 2log_{2}(n+1) height.

**Operations on red-black tree**

- Insertion
- Deletion
- Searching

__Height balanced (AVL) tree VS red-black tree__

- A red-black tree with n internal nodes has height at most 2log
_{2}(n+1). - An AVL tree with n internal nodes has height at most 1.44log
_{2}n . - An AVL tree is a kind of a red-black tree.All AVL trees satisfy the properties of a red-black tree but all red-black trees are not AVL trees.
- A red-black tree is a kind of B-tree.