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
Example 2 Height balanced 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
- 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:
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
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.
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
- 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:
- Every node is either red or black.
- The root is always colored with black.
- Every external node is black.
- If a node is red then,both its children are black.
For each node,all paths from that node to descendant external nodes contain the same number of black nodes.
- The number of black ancestors from an external node to any node is defined as the black depth.
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
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.