AVL Trees

• Binary search tree which can reach worst-case time complexity of O(log n).
• An AVL Tree is a Binary Search Tree in which, for all nodes in the tree, the heights of the two child subtrees of the node differ by at most one. If, at any time, the two subtree heights differ by more than one, rebalancing is done to restore this property.
• The balance factor of a node u is equal to the height of u's right subtree minus the height of u's left subtree
• for all nodes u in the tree, the balance factor of u is either -1, 0, or 1
• AVL Rotations: can be done in two directions: right or left.
• Remove():
  1. first perform the regular BST removal algorithm.
  2. Then, starting at the parent of whatever node was actually removed from the tree, traverse up the tree and update each node's balance factor.
  3. For any nodes that are now "out of balance," perform AVLs rotation to fix the balance.
• double rotation, which is simply a series of two AVL rotations that will be able to fix the tree's balance.

REFERENCE: Stepik 3.6