AVL Tree

AVL Tree

• self-balancing Binary Search Tree
  • the tree balances itself when a new node is inserted and deleted
  • it follows the general properties of a BST
• the balance factor
  • the difference between the heights of left and right subtrees of any node <= 1
  • it mainly uses rotations to maintain both BST properties and height balance
  • height <= log(n) (n is total number of nodes)
  • the time complexities of all operations (search, insert, delete, max, min, floor, ceiling) become O(logN)
  • this happens because height of an AVL tree is bounded by O(logN)
  • in BST, it can be go up to O(N)
• it has better searching time complexity than other trees so...
  • most in-memory sets and dictionaries are sorted using AVL Trees
  • database application where insertions and deletions are less more common but frequent data lookups are necessary, also frequently employ AVL Trees
  • c/c++에서 제공하는 stl이라는 라이브러리에서 sorting을 구현할 때도 avl 트리가 사용되는듯 (set, map등등) 
• every AVL tree is BST but every BST is not AVL tree
  • left subtree values are smaller and right subtree values are greater for every node
  • this is not AVL Tree
    • the balance factor of the node 8 -> 4

BST but not AVL Tree

 

 

• whereas this is AVL Tree. 
  • the balance factor of the node 12, 8, 18, 5 -> 1
  • the balance factor of the node 11, 17, 4 -> 0

 

BST and also AVL Tree

 

Operations on an AVL Tree

• search : we can use the same implementation as BST
• insert / delete : it does rotations along with normal BST inseretion/deletion to make use that the balance factor of the impacted nodes is less sthan or equal to 1.

Rotating subtrees

• Left rotation 

• Right rotation

 

• Left-Right rotation

 

• Right-Left rotation

 

• since the balancing rules are strict compared to Red Black Tree, AVL trees in general have relatively less height and hence the search is faster
  • implement level : BST < AVL < RBTree
  • searching velocity : RBTree < AVL
  • strictness of balancing rule : AVL < RBTree

 

RBTree와 비교

RBTree도 AVL처럼 LL, RR, LR, RL 네 가지 회전을 모두 사용한다. 그러나 AVL은 balance factor가 깨질 때마다(높이 불균형 발생할 때마다) 항상 회전해줘야 하는데 RBTree는 black height가 다를 때 or red가 연속될 때만 회전해주면 된다. 그리고 AVL은 위로 올라가면서 계속 회전시켜야 하는데 RBTree는 회전 후에 색상만 바꿔주면 끝나는 경우가 많으므로 AVL보다 RBTree의 회전 빈도가 더 적다.

 

여기서 알 수 있는 점은 AVL은 엄격하게 균형을 유지해서 탐색 성능은 좋지만

그 정도의 균형 유지를 위해 트리 조정을 너무 많이 하게 되므로 삽입/삭제 성능은 좋지 않다는 점이다.

 

 

https://www.geeksforgeeks.org/introduction-to-avl-tree/