Advanced Trees
————————
Definition of an AVL tree: An AVL tree is a binary search tree which has the following properties:
1. The sub-trees of every node differ in height by at most one.
2. Every sub-tree is an AVL tree.
Named after their inventors, Adelson-Velskii and Landis, they were the first dynamically balanced trees to be proposed.
Features of AVL Trees
——————————–
AVL Trees are derived from binary search trees by applying one condition; the difference of height between the left and right sub-trees should not exceed 1.
These types of binary trees are also called Balanced binary trees.
The balance factor can have values of –1, 0 and 1. If the balance factor holds any other values, then it is not considered as an AVL tree. The three values given above represent different conditions of AVL trees. They are –
1. balance = -1: the height of the left sub-tree of the current node is less than its right sub-tree by 1.
2. balance = 0: the heights of the left and right sub-trees of the current node are equal
3. balance = 1: the height of the left sub-tree is one more than the right sub-tree
Representation of AVL Trees
——————————————
struct AVL
{
struct AVL *left;
int value;
struct AVL *right;
int balance;
};
Insertion of a Node
———————————-
Inserting a node in an AVL tree is similar to the binary search tree.
To balance a tree, an operation called rotation is performed
Inserting a node may change the balancing factor of other nodes and thus may not satisfy the conditions of the AVL tree.
To balance a tree, an operation called rotation is performed.
To rotate the tree about a node is to move the nodes either left or right so that the inorder traversal remains the same.
Deletion of a node
——————————
The deletion performed on a node in AVL tree is the same as that of the deletion process of the Binary search tree.
First the node to be deleted is searched using the binary search method.
The node is deleted and other nodes are adjusted to maintain the inorder traversal.
After the node is deleted, balancing operation is performed which is the same as of that done during the insertion operation.
Definition of a B tree
————————————
A B-tree is a data structure that maintains an ordered set of data and allows efficient operations to find, delete, insert, and browse the data. In this discussion, each piece of data stored in a B-tree will be called a “key”, because each key is unique and can occur in the B-tree in only one location
Representation of B Trees
————————————-
struct Bnode
{
int n;
int value[MAX + 1];
struct Bnode *child[MAX + 1];
};
Operations on B-Trees
———————————-
When the tree is large and stored in secondary storage medium, the searching operation may consume time.
One way of reducing the time is to take up many nodes for comparison. As a result Multi-way search trees were developed.
1. Insertion operation in B-tree
2. Deletion process in B-tree
Insertion operation in B-tree: To insert a value in a B-tree, the node in the tree after which it can be inserted is searched first. Once the node is found, insertion process begins.
Deletion operation in B-tree: To delete a node, first the value to be deleted is searched. Once the node, which contains the value, is found the deletion process starts. There are some conditions that has to be taken care after deleting a node.
Conditions on Deletions
——————————–
When the number of values in the current node is greater or equal to the minimum number the node has to hold. In this case, the deletion of the node does not violate the conditions for the B-tree
When the number of values in the current node is less than the minimum number the node has to hold. Here the tree has to be adjusted so that the conditions for the B-tree is not violated.
