What Is AVL Tree | Get Help In Data Structure Algorithms



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:

  1. Method FindKey (int tkey, boolean found).

  2. Method Insert (int k, Type e, boolean inserted).

  3. Method Remove_Key (int tkey, boolean deleted)

  4. Method Update(Type e)

  5. Method Traverse (Order ord)

  6. Method DeleteSub ( )

  7. Method Retrieve (Type e)

  8. Method Empty (boolean empty).

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







9 views0 comments