Algorithms & Data Structures - AVL TREE

• A balance binary search tree.
• The best search time, that is O(log N) search times


• An AVL tree is defined to be a well-balanced binary search tree in which each of its nodes has the AVL property.
• The AVL property is that the heights of the left and right sub-trees of a node are either equal or if they differ only by 1

Keeping the Tree Balance

• the height of the right subtree and height of the left subtree for any node cannot differ by more than one.
• This process is usually done through rotation.

Diagram 1


• A single counter clockwise rotate will balance it.
• s_ right_rotate() - because it involves the right subtree.

Diagram 2


• A single counter clockwise rotate will balance it.
• s_ left_rotate() - because it involves the left subtree.

Diagram 3


• A double clockwise rotate will balance it.
• 1st - single clockwise rotation with the parent of the inserted node (this produces the tree in diagram 1)
• 2nd - single counter clockwise rotation on the root
• d_ right_rotate() - because it involves the right subtree.

Diagram 4


• A double clockwise rotate will balance it.
• 1st - single counter clockwise rotation with the parent of the inserted node (this produces the tree in diagram 2)
• 2nd - single clockwise rotation with the root.
• d_ left_rotate() - because it involves the left subtree.

Example:
Given these data: build an AVL tree.
12 , 10 , 3 , 23 , 11, 14 , 2 , 4 , 1
Click the picture below to see the answer! ^_^