Go through below points to know clear explanation about AVL Tree:
Height: the longest path from a node to a leaf node.
Height-balanced tree: A binary tree is a height-balanced-p-tree if for each node in the tree, the absolute difference in height of its two subtrees is at most p.
AVL tree is a BST that is height-balanced-1-tree.
For each node in the tree, the absolute difference in height of its two subtrees must be at most 1.
Balance = Right Subtree Height – Left Subtree Height
Therefore, it must be either +1 (longer right), 0 (equal), -1 (longer left).
AVL Tree Specification
Elements: The elements are nodes, each node contains the following data type: Type.
Structure: Same as for the BST; in addition the height difference of the two subtrees of any node is at the most one.
Domain: the number of nodes in a AVL is bounded; type AVLTree.
Operations:
Method FindKey (int tkey, boolean found).
Method Insert (int k, Type e, boolean inserted).
Method Remove_Key (int tkey, boolean deleted)
Method Update(Type e)
Method Traverse (Order ord)
Method DeleteSub ( )
Method Retrieve (Type e)
Method Empty (boolean empty).
Method Full (boolean full)
AVL Tree Element
public class AVLNode<T> {
public int key
public T data;
public Balance bal; // Balance is enum (+1, 0, -1)
public AVLNode<T> left, right;
public AVLNode(int key, T data) {
this.key = key;
this.data = data;
bal = Balance.Zero;
left = right = null;
}
...
...
}
AVL Tree Implementation
The implementation of: FindKey, Update data, Traverse, Retrieve, Empty, Full, and any other method that doesn’t change the tree are exactly like the implementation of BST.
The only difference in implementation is when we change the nodes of the tree, i.e. Insert/Remove from the tree.
AVL Tree Insert
Step 1: A node is first inserted into the tree as in a BST.
Step 2: Nodes in the search path are examined to see if there is a pivot node. Three cases arise.
search path is a unique path from the root to the new node.
pivot node is a node closest to the new node on the search path, whose balance is either –1 or +1.
Case 1: There is no pivot node in the search path. No adjustment required.
Case 2: The pivot node exists and the subtree to which the new node is added has smaller height. No adjustment required.
Case 3: The pivot node exists and the subtree to which the new node is added has the larger height. Adjustment required.
Case 1: Insert 40
Case 1: Insert 55
Case 2: Insert 5
Case 2: Insert 45
Case 2: Insert 45
Insert Case 3:
When after an insertion or a deletion an AVL tree becomes imbalanced, adjustments must be made to the tree to change it back into an AVL tree.
These adjustments are called rotations.
Rotations can be in the left or right direction.
Rotations are either single or double rotations
Therefore, there are four different rotations:
Left Rotation (Single)
Right Rotation (Single)
Left-Right Rotations (Double)
Right-Left Rotations (Double)
AVL Tree Delete
Step 1: Delete the node as in BSTs. Remember there are three cases for BST deletion.
Step 2: For each node on the path from the root to deleted node, check if the node has become imbalanced; if yes perform rotation operations otherwise update balance factors and exit. Three cases can arise for each node p, in the path.
Case 1: Node p has balance factor 0. No adjustment required.
Case 2: Node p has balance factor of +1 or –1 and a node was deleted from the taller sub-trees. No adjustment required.
Case 3: Node p has balance factor of +1 or –1 and a node was deleted from the shorter sub-trees. Adjustment required.
Case 1: Delete 60
Case 1: Delete 50
Comentarios