[자료구조] Balanced BST(균형이진탐색트리)의 정의와 종류

[자료구조] Balanced BST(균형이진탐색트리)의 정의와 종류

 

 

살펴볼 주요 개념:

• Balanced BST의 정의
• Balanced BST의 종류

 

1. Balanced BST의 정의

같은 키값을 가지는 BST와 BBST

Balanced BST(균형이진탐색트리, 이하 BBST)는 BST(이진탐색트리)가 위의 사진처럼 데이터 추가로 인해 길이가 과도하게 길어진 편향적인 이진 탐색트리를 방지하기 위해 만들어졌다.

 

높이는 탐색, 삽입과 삭제 연산에 영향을 미치게 된다. 노드의 탐색 시간이 많이 걸릴 수록 삽입과 삭제연산도 이에 영향을 받아 수행시간이 오래 걸릴 수 있다. 그렇기 때문에 높이는 최소한으로 하면서 트리에 데이터를 삽입, 삭제하는 것이 필요하다.

 

위의 사진의 경우를 보면 왼쪽의 BST에서는 15에서 8까지 가는 것에 에지를 4번 거쳐야 하지만, BBST는 최악의 경우인 8에서 3 또는 15까지 가는 것에도 2번의 링크만 거치면 된다.

 

이렇게 BBST는 최악의 경우에도 높이는 O(logN)로 맞출 수 있게 된다.

 

다만 새로운 데이터가 추가 될 때, 노드들을 로테이션 시켜주는 것이 필요하다.

로테이션이라고 해도, 링크를 총 6개 수정해주는 것에 불과하다.

 

 

* BBST의 로테이션

 

** 로테이션 구현

BST 트리가 있다는 가정하에 메소드를 만들어 보았다.

BST 트리 구현 코드는 아래를 참조하면 되겠다.

 

2022.05.15 - [프로그래밍/자료구조] - [자료구조] Binary Search Tree(BST, 이진탐색트리) 정의와 python 구현

 

def rotateRight(self, z): # self : BST, z : 기준점)
    if not z: # 기준점이 없으면 종료
        return
    x = z.left
    if x == None: # 기준점의 왼쪽 서브트리가 없는 경우 종료
        return
    b = x.right
    x.parent = z.parent # x 왼쪽 위에 있는 링크 중 원래 z의 부모로 향하는 링크 수정
    if z.parent: # z가 루트노드가 아니었던 경우
        if z.parent.left == z: # z가 z부모의 왼쪽 노드였다면 
            z.parent.left = x # z부모 왼쪽에 x를 연결
        else:
            z.parent.right = x # z가 z부모의 오른쪽 노드였다면 오른쪽에 x연결
    x.right = z # x에서 z로 내려가는 링크 수정
    z.parent = x # z에서 x로 올라가는 링크 수정
    z.left = b # z에서 b로 내려가는 링크 수정
    if b: # b가 있는 경우(없는 경우는 z.left = None이 되고 끝)
        b.parent = z #z에서 b로 올라가는 링크 수정
    if self.root == z: # z가 루트 노드였다면
        self.root = x # x를 루트노드로 수정

 

 

 

2. Balanced BST의 종류

 

• Adelson Velsky Landis Tree(AVL Tree)

모든 노드에 대해서 각 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차가 1 이하인 BST

 

• Red-Black Tree

가장 유명하고 많이 사용하는 균형이진탐색트리. 빨간색과 검정색 노드를 활용하며, 노드의 색깔에 규칙을 둔다.

leaf노드가 없는 경우(None), nil 노드를 모든 leaf 노드에 배치한다.

 

• 2, 3, 4 Tree

이진트리가 아닌 탐색트리이다.

자식노드가 2개 또는 3개 또는 4개이다.

 

 

 

등등 많다.