0
1.8kviews
Discuss AVL Trees.
1 Answer
0
14views
  • A binary tree is a data structure in which every node has no more than two descendent nodes and no more than one parent node.
  • A binary search tree is a binary tree in which a node’s left child node has a value less than its and the node’s right node has a value greater than its.
  • 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.

  • In this example, every left subtree has a height one greater than each right subtree

enter image description here

  • The motivation of AVL trees was to guarantee a height of log(n) so that insertions and deletions always occur at O(log(n)).
  • A balanced factor is an integer which is associated with each node of the tree. It indicates weather a tree is left-heavy (height of left subtree is greater than that of right subtree), balanced (both subtress are of the same height), or right-heavy(opposite of left-heavy).
  • Balance factor of a node = height othe left subtree - the height of the right subtree
  • Each node of an AVL tree can have a balanced factor of -1, 0 or +1 only.
  • If the balanced factor’s magnitude exceeds 1 after an operation such as insertion or deletion, then balancing is required. This is done with the help of rotations.
  • There are basically 4 types of imbalance cases and 2 types of rotations to make the tree balanced.

enter image description here

enter image description here

Please log in to add an answer.