Books Online Courses
Free Tutorials  Go to Your University  Placement Preparation 
Latest:- Important tips to get an Off Campus Placements
0 like 0 dislike
in Examples, Exercises and Projects by (562 points)
retagged by

In this article,you will get to know about:

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

1 Answer

0 like 0 dislike
by (562 points)
edited by
Best answer

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


Height balanced tree

height balanced binary tree


Balance factor








Example 2 Height balanced tree

height balanced binary tree


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








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


  • 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

node structure of height balanced tree

  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)


  • 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:

node tree

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


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


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.


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


red-black tree

Height of the red-black tree:

A red-black tree with n internal nodes has at most 2log2(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 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. 

3.3k questions

7.1k answers


4.6k users


About Us | Contact Us || Terms & Conditions | Privacy Policy || Youtube Channel || Telegram Channel © Social::   |  |