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

Question

In this article,you will get to know about:

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

Answer 1

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

---

2. 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

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₂(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₂(n+1).
• An AVL tree with n internal nodes has height at most 1.44log₂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. 

  ---