AVL tree

From Algorithmist
Jump to: navigation, search

Summary[edit]

AVL tree is binary search tree whose height is of the order of O(log n), and it guarantees data insertion, retrieval and removal times of the order of O(log n) where n is the number of nodes in the tree. AVL tree is a efficient data structure which can be used for fast retrieval of data.

Explanation[edit]

The tree is able to provide O(log n) transactions because the tree is close to be a complete binary tree. Height of left subtree and right subtree of any node in AVL tree is never greater than 1. If the insertion or deletion of any node in the tree violate the balance factor of the node i.e. it balance factor becomes greater than one then the tree around the node has to be restructured using one of the tree rotation techniques. There are four types of rotations possible in a AVL tree viz. right-right rotation(RR), right-left(RL) rotation, left-left rotation(LL), and left-right rotation(LR). The RR and LL rotations are mirror images and the RL and LR rotations are mirror images of each other.

Gotchas[edit]

  • Any points one can easily overlook?
  • The correct way to understand ambiguous formulations?

Notes[edit]

  • Anything special to note about the problem.

Implementations[edit]

Notes/Hints on actual implementation here.

Optimizations[edit]

Optimizations here.

Input[edit]

Input Here

Output[edit]

Output Here

References[edit]

  1. Reference 1

Categories here, use the form [[Category: Category Name]], see Categories for a list