# What do you mean by height balanced binary tree and B trees in data structure and algorithms?

0 like 0 dislike
2.7k views

retagged

1. Height balanced binary tree
2. B trees
3. B+ tree
4. Red black tree

0 like 0 dislike
by (562 points)
edited

# 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(hl)-height of right sub-tree(hr)
• So, in a height balanced binary search tree all the nodes have a balance factor.
• |bf|=|hl-hr|≤ 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

1. # 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:

• where

Ki(1≤i≤n) are the key values.

Pi(0≤i≤n) are printers to the subtree of T.

Ki<Ki+1 , 1≤i<n

• All the key values in the sub-tree pointed by Pi are less than the key Ki+1 , 0≤i<n
• All the key values in the sub-tree pointed by Pn is greater than Kn.
• All the sub-trees pointed by Pi(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

• 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 ith child's sub-tree(2=i=K)are between the (i-1)th key of n and the ith 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 2log2(n+1) height.

• Insertion
• Deletion
• Searching

## Height balanced (AVL) tree VS red-black tree

• A red-black tree with n internal nodes has height at most 2log2(n+1).
• An AVL tree with n internal nodes has height at most 1.44log2n .
•  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.