Tree 3

Complexity of Tree Operations

• Lookup Time

  • Balanced Tree : O(log n)
  • Unbalanced Tree : O(n)

• Insertion Time

  • Balanced Tree : O(log n)
  • Unbalanced Tree : O(n)

---

AVL Tree

• A Self-balancing binary search tree.
• Height : O(log n)
• For every node v of the tree T, the heights of the children of v differ by at most 1.

Insertion

1. same as in a binary search tree.
2. after insertion, all nodes along the path increases their height by 1.
3. It may violate AVL tree.
   -> So, rebalance the subtree of z using a restructuring method.

z : the first violation node along the path.
y : z's child with higher height.
x : y's child with higher height.
(a, b, c) : inorder traversal of node x, y, and z.

Restructing

1. Single rotation
   (1) a = x, b = y, c = z
   (2) a = z, b = y, c = x
2. Double rotation
   a = z, b = x, c = y : (1)꼴로 만든 후 rotate
   a = y, b = x, c = z : (2)꼴로 만든 후 rotate

Removal

z : The first unbalanced node encountered while travelling up the tree from the violating node w.
y : The child of z with the higher height.
x : The child of y with the higher height.

Removal can be happened everywhere insied the tree. So, compare to insertion, it needs recursive reconstructing, keep checking for balance until the root is reached.

---

AVL Tree Performance

• Restructing
  • A single restructure takes O(1) time.
  • Using a linked-structure binary tree.
• Search
  • A search takes O(log n) time.
  • The height of tree is O(log n), no restructuring is needed.
• Insertion
  • An insertion takes O(log n) time.
  • Restructuring up the tree, maintaining heights is O(log n).
• Deletion
  • A deletion takes O(log n) time.
  • Restructuring up the tree, maintaining heights is O(log n).