Binary Search Tree (BST)와 AVL Tree

Binary Search Tree (BST)

이진 검색 트리는 정렬된 트리 데이터 구조이다.

 

모든 부모 노드에는 최대 두 개의 자식 노드가 있으며,

부모 노드의 왼쪽 자식 노드는 항상 부모 노드보다 작고 오른쪽 자식 노드는 항상 부모 노드보다 크다.

 

모든 트리 자료구조와 같이 이진 검색 트리는 Root가 있고(최상단 노드),

부모 노드에는 최대 두 개의 자식 노드들이 있으며 이것을 Siblings라고 한다.

 

노드 사이의 연결을 edge라고 하고, 자식이 없는 노드를 leaf라고 한다.

 

이진 검색 트리는 순차적으로 정렬된 자료구조로서, 데이터 삽입 시 노드가 순서대로 배치된다.

따라서 이러한 정렬된 순서는 검색을 빠르게 만든다.

 

배열과 달리 데이터는 참조 형식으로 저장된다.

자료구조에 저장할 때, 우리는 메모리에 새로운 공간을 만들고 연결한다.

 

BST는 검색, 더하기, 삭제에서 O(log n)의 시간 복잡도를 가진다.

하지만 정렬된 리스트를 더하는 경우 O(n)의 시간 복잡도를 가지게 된다(최악의 경우에서의 시간 복잡도에 해당).

 

이러한 문제를 해결하기 위해 AVL Tree가 해답이 될 수 있다.

구현

이진 검색 트리와 노드 클래스를 만든다면 아래와 같다.

노드는 value와 왼쪽, 오른쪽 속성을 가지고 트리는 root 속성을 가진다.

class Node {
  constructor(value){
      this.value = value
      this.left = null
      this.right = null
  }
}

class BinarySeachTree {
      constructor(){
        this.root = null
      }
}

AVL Tree

발명가인 Georgy Adelson-Velsky와 Evgenii Landis의 이름을 따서 명명되었다.

 

AVL 트리는 노드의 두 자식 노드의 높이 차이가 둘 이상 다를 수 없는 자체 균형 BST이다.

따라서 둘 이상의 차이가 난다면 이 특성을 유지하기 위해 재조정을 수행한다.

 

발명된 이유

대부분의 BST 연산(예: 검색, 최댓값, 최솟값, 삽입, 삭제...)은 O(h)의 시간 복잡도를 가진다(h: BST 트리의 높이).

하지만 어느 한쪽 방향으로 트리가 편향된 경우, 이러한 연산은 O(n)이 될 수 있다.

 

이러한 작업의 상한선이 O(log n)으로 유지되도록 하려면 모든 삽입 및 삭제 후에 트리의 높이가 O(log n)을 유지하도록 해야 한다.

 

따라서 트리의 높이가 항상 O(log n)인지 확인하는 AVL 트리가 발명되었다.

 

Balance factor (균형 계수)

AVL 트리에서 각 노드는 값이 -1, 0, +1인 균형 계수라고 하는 추가 정보를 가지고 있다.

AVL 트리에서 노드의 균형 계수는 해당 노드의 왼쪽 자식 노드 트리와 오른쪽 자식노드 트리의 높이 간 차이이다.

---

Balance factor = 왼쪽 자식노드 트리 높이 - 오른쪽 자식노드 트리 높이

 

AVL 트리의 자체 균형 속성은 균형 계수에 의해 유지된다.

균형 계수의 값은 항상 -1, 0, +1이어야 한다.

 

Operations on AVL Tree

하위 트리의 노드 위치를 교환할 수 있는 두 가지 유형의 회전이 있다.

 

Left Rotate

왼쪽 회전에서는 오른쪽 노드의 배열이 왼쪽 노드의 배열로 변환된다.

 

Step

1. 초기
   

   

2. 만약 y가 왼쪽 하위 트리를 가지면, X를 왼쪽 하위 트리의 부모 노드가 되게 한다.
   

   

3. 만약 X의 부모 노드가 NULL이라면, Y를 트리의 root로 만든다.
4. 그렇지 않고 X가 P의 왼쪽 자식 노드라면, Y를 P의 왼쪽 자식 노드로 만든다.
5. 그렇지 않으면 Y를 P의 오른쪽 자식노드로 만든다.
   

   

6. Y를 X의 부모 노드로 만든다.
   

   

오른쪽 회전도 같은 원리로 수행한다.

Left-Right and Right-Left Rotation

좌우 회전에서는 배열이 먼저 왼쪽으로 이동한 다음 오른쪽으로 이동한다.

1. x-y 좌회전
   

   

2. y-z 우회전
   

   

우 좌회전도 같은 원리!

AVL Tree에 node 삽입하기

새 노드는 항상 균형 계수가 0인 leaf 노드로 삽입된다.

1. 초기 트리와 삽입될 노드
   

   

2.  새 노드의 값  newKey와 rootKey를 비교한다.
   newKey < rootKey: 왼쪽 하위 트리에 대한 삽입 알고리즘을 leaf 노드를 찾을 때까지 반복한다.
   newKey > rootKey: 오른쪽 하위트리에 대한 삽입 알고리즘을 leaf 노드를 찾을 때까지 반복한다.
   같다면 leaf 노드를 반환한다.
3. leafKey와 newKey를 비교한다.
   newKey < leafKey: 새 노드를 leaf 노드의 왼쪽 자식 노드로 만든다.
   newKey > leafKey: 새 노드를 leaf 노드의 오른쪽 자식노드로 만든다.
   

   

4. 균형 계수를 업데이트한다.
   

   

5. 균형 계수가 2 이상인 지점이 있다면 회전 작업을 수행한다.
   

   

Removing a node from AVL Tree

노드는 항상 leaf 노드로 삭제된다.

노드를 삭제하면 노드의 균형 계수가 변경되며, 이에 따른 균형 계수의 균형을 재조정하기 위한 회전 작업을 수행한다.

 

1. nodeToBeDeleted를 재귀적으로 찾는다.
   

   

2. 노드를 삭제하는 세 가지 경우가 있다.
   1) 만약 nodeToBeDeleted가 leaf 노드라면, 바로 삭제한다.
   2) 만약 nodeToBeDeleted가 하나의 자식 노드를 가진다면, 자식 노드가 그 자리를 대체하고 자식 노드를 삭제한다.
   3) 만약 nodeToBeDeleted가 두 개의 자식노드를 가진다면, 오른쪽 하위 트리의 최솟값을 가진 노드로 대체한다(Successor Node).
3. Successor node를 찾는다.
   

   

4. 현재 노드를 제거한다.
   

   

5. 균형 계수를 업데이트한다.
6. 균형 계수가 -2 이하 또는 2 이상일 때 재조정한다.
   

   

 

 

 

 

 

출처

https://learnersbucket.com/tutorials/data-structures/avl-tree-in-javascript/

AVL Tree in Javascript - LearnersBucket