Binary Search Tree의 구현

현굥·2024년 7월 28일

algorithm

목록 보기

1/17

이진 탐색 트리 (Binary Search Tree, BST)

이진 탐색 트리는 각 노드가 최대 두 개의 자식을 갖는 이진 트리로서, 다음과 같은 특징을 가지고 있습니다.

BST의 특징:

노드 insertion 및 search 시간 복잡도: 평균적으로 삽입과 검색이 O(log n)의 시간 복잡도를 가집니다. (n은 노드의 수)
정렬된 데이터 저장: BST는 각 노드의 왼쪽 서브트리의 모든 값이 해당 노드의 값보다 작고, 오른쪽 서브트리의 모든 값이 해당 노드의 값보다 크기 때문에 데이터가 항상 정렬된 상태를 유지합니다.

BST의 구현

Node

이진트리의 노드를 정의하는 클래스인 Node 를 구현해봅시다. 각 노드는 다음과 같은 속성을 가지고 있습니다.

key: 노드의 키 값
left: 현재 노드의 왼쪽 자식 노드를 가리키는 포인터
right: 현재 노드의 오른쪽 자식 노드를 가리키는 포인터
parent: 현재 노드의 부모 노드를 가리키는 포인터

code


class Node:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None
        self.parent = None

BST

이제 BST 클래스를 구현해봅시다.

BST 클래스는 다음과 같은 메서드로 정의되어 있습니다.

tree_insert(): 새로운 노드를 삽입합니다.
tree_search(): 트리에서 특정 키를 가진 노드를 찾습니다.
iterative_tree_search() : 반복문을 사용하여 트리에서 원하는 키값을 가진 노드를 찾습니다.
tree_minimum() : 서브트리에서 최소값을 찾습니다.
tree_maximum() : 서브트리에서 최대값을 찾습니다.
tree_successor() : 특정 노드의 후속자를 찾습니다.
inorder_tree_walk() : 트리를 중위 순회합니다.
transplant() : 한 노드를 다른 노드로 대체합니다.
tree_delete() : 트리에서 특정 노드를 삭제합니다.
print_tree() : 이진 탐색 트리를 인쇄합니다.

전체 코드는 다음과 같습니다.

code

class BST:
    def __init__(self):
        self.root = None

    def tree_insert(self, z):
        y = None
        x = self.root
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

    def tree_search(self, x, k):
        if x is None or k == x.key:
            return x
        if k < x.key:
            return self.tree_search(x.left, k)
        else:
            return self.tree_search(x.right, k)

    def iterative_tree_search(self, x, k):
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

    def tree_minimum(self, x):
        while x.left is not None:
            x = x.left
        return x

    def tree_maximum(self, x):
        while x.right is not None:
            x = x.right
        return x

    def tree_successor(self, x):
        if x.right is not None:
            return self.tree_minimum(x.right)
        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

    def inorder_tree_walk(self, x):
        if x is not None:
            self.inorder_tree_walk(x.left)
            print(x.key, end=' ')
            self.inorder_tree_walk(x.right)

    def transplant(self, u, v):
        if u.parent is None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v is not None:
            v.parent = u.parent

    def tree_delete(self, z):
        # Determine which node to splice out: either z or z’s successor
        if z.left is None or z.right is None:
            y = z  # case 0 or 1
        else:
            y = self.tree_successor(z)  # case 2

        # Set x to a non-NIL child of y, or to NIL if y has no children
        if y.left is not None:
            x = y.left
        else:
            x = y.right

        # y is removed from the tree by manipulating pointers of p[y] and x
        if x is not None:
            x.parent = y.parent

        if y.parent is None:
            self.root = x
        elif y == y.parent.left:
            y.parent.left = x
        else:
            y.parent.right = x

        # If z’s successor was spliced out, copy its data into z
        if y != z:
            z.key = y.key
            # Here you would also copy any other satellite data from y to z

        return y

    def print_tree(self):
        self._print_tree_recursive(self.root, 0)

    def _print_tree_recursive(self, node, level):
        if node is None:
            return
        self._print_tree_recursive(node.right, level + 1)
        print('  ' * level + str(node.key))
        self._print_tree_recursive(node.left, level + 1)

각각의 함수과 코드에 대해 설명해보겠습니다.

tree_insert()

  def tree_insert(self, z):
        y = None
        x = self.root
        while x is not None:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y is None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z

위 코드는 이진 탐색 트리에 새로운 노드를 삽입하는 tree_insert 메서드를 구현한 것입니다. 이 메서드는 주어진 노드 z를 트리에 삽입합니다. 코드의 동작은 아래와 같습니다.
1. 먼저, 삽입할 위치를 찾기 위해 트리를 탐색합니다. 이를 위해 현재 노드를 나타내는 x를 루트부터 시작하고, x가 None이 될 때까지 반복하여 적절한 위치를 찾습니다. 동시에 y는 x의 부모 노드를 나타냅니다.
2. x가 None이 되어 탐색이 종료되면, y가 새로운 노드 z의 부모 노드가 됩니다. 따라서 z.parent를 y로 설정합니다.
3. 만약 y가 None이라면, 삽입할 노드가 트리의 첫 번째 노드이므로 z를 트리의 루트로 설정합니다.
4. 그렇지 않고, z의 키 값이 y의 키 값보다 작으면 z를 y의 왼쪽 자식으로 삽입합니다.
5. 그렇지 않으면(z의 키 값이 y의 키 값보다 크거나 같으면), z를 y의 오른쪽 자식으로 삽입합니다.

이러한 방식으로 tree_insert()는 이진 탐색 트리의 성질을 유지하면서 새로운 노드를 적절한 위치에 삽입합니다.

tree_search()

이진탐색트리에서 특정 키k를 찾기 위해 사용되는 재귀함수입니다.

코드의 동작은 아래와 같습니다.

현재 노드 x가 None인 경우, 이것은 트리의 끝에 도달하여 키를 찾지 못한 경우입니다. 이 경우에는 해당 서브트리에 키가 없음을 나타내기 위해 None을 반환합니다.
현재 노드 x의 키가 대상 키 k와 같은 경우, 우리는 원하는 키가 있는 노드를 찾았으며 이 노드를 반환합니다.

 def tree_search(self, x, k):
        if x is None or k == x.key:
            return x
        if k < x.key:
            return self.tree_search(x.left, k)
        else:
            return self.tree_search(x.right, k)

iterative_tree_search()

이진 탐색 트리(BST)에서 특정 키 k를 반복적으로 탐색하는 함수입니다.

코드의 동작은 아래와 같습니다.

while 루프를 사용하여 노드 x가 None이 아니고 대상 키 k가 현재 노드 x의 키와 다를 때까지 반복합니다. 이는 트리를 왼쪽이나 오른쪽으로 순회하면서 키를 찾거나 끝까지 도달할 때까지 반복합니다.
각 반복에서는 현재 노드 x의 키와 대상 키 k를 비교하여 다음 이동할 방향을 결정합니다.
- 대상 키 k가 현재 노드의 키보다 작으면 왼쪽 서브트리로 이동합니다.
- 대상 키 k가 현재 노드의 키보다 크면 오른쪽 서브트리로 이동합니다.
- 만약 대상 키 k가 현재 노드의 키와 같다면, 원하는 키를 찾았으므로 루프를 종료합니다.
루프가 종료되면 현재 노드 x를 반환합니다. 이는 대상 키를 찾았을 경우 해당 키를 가진 노드를 반환하고, 찾지 못했을 경우 None을 반환합니다.

  def iterative_tree_search(self, x, k):
        while x is not None and k != x.key:
            if k < x.key:
                x = x.left
            else:
                x = x.right
        return x

tree_minimum() , tree_maximum()

이진 탐색 트리(BST)에서 특정 노드 x를 루트로 하는 서브트리에서 가장 크거나, 가장 작은 키 값을 가진 노드를 찾는 함수입니다.
tree_minimum()의 동작은 아래와 같습니다. tree_maximum()의 경우에도 왼쪽과 오른쪽만 바꾸어 생각하면 됩니다.

주어진 노드 x의 왼쪽 자식이 None이 될 때까지 반복합니다. 이 과정은 x의 왼쪽 자식이 없는, 즉 현재 노드가 해당 서브트리에서 가장 작은 키를 가진 노드임을 보장합니다.
반복이 종료되면 현재 노드 x를 반환합니다. 이는 가장 작은 키를 가진 노드를 찾았음을 의미합니다.

#  tree_minimum
def tree_minimum(self, x):
        while x.left is not None:
            x = x.left
        return x

#  tree_maximum
    def tree_maximum(self, x):
        while x.right is not None:
            x = x.right
        return x

tree_successor()

노드 x의 후계자를 찾습니다. 후계자란, BST에서 주어진 노드 ‘x’ 보다 크면서 가장 작은 값을 가진 노드를 의미합니다.

이 함수는 BST에서 삭제 연산을 수행할 때 유용하게 사용됩니다.

BST의 삭제연산에 대해 미리 추가적인 설명을 해보자면, BST의 삭제 연산은 다음과 같이 세 가지 경우로 나누어집니다.

Case 0: 삭제할 노드가 자식이 없는 경우
Case 1: 삭제할 노드가 한 개의 자식을 가진 경우
Case 2: 삭제할 노드가 두 개의 자식을 가진 경우

tree_successor() 는 위 세가지 경우 중 Case 2에서만 사용되며, 이 경우 삭제할 노드를 대체할 successor를 찾아야 합니다. 후계자는 삭제할 노드를 대체하여 BST의 특성을 유지하면서 빈 자리를 채우는 역할을 합니다.

#참고

💡 **Case 2 :** 삭제 연산 시 successor 를 찾는 과정

삭제할 노드의 오른쪽 서브트리에서 가장 작은 키를 가진 노드를 찾습니다. 이 작업은 tree_successor()를 호출하여 수행됩니다.
후계자를 찾은 후, 해당 노드의 키를 삭제할 노드에 복사합니다.
후계자 노드를 삭제하고, 삭제할 노드가 있던 자리를 후계자로 채웁니다.

위의 과정 중 첫번째 과정에 tree_successor()는 BST에서 삭제 연산을 수행할 때 후계자를 찾는 데 사용됩니다.

tree_successor 의 동작방식은 아래와 같습니다.

먼저 주어진 노드 x의 오른쪽 서브트리가 비어있지 않은지 확인합니다. 오른쪽 서브트리가 비어있지 않다면, 그 서브트리에서 가장 작은 값을 찾기 위해 tree_minimum 메서드를 호출합니다. 이 값이 후계자가 됩니다.

만약 오른쪽 서브트리가 비어있는 경우, 후계자를 찾기 위해 부모 노드를 따라 올라가면서 검색합니다. 이때, 다음의 두 가지 경우가 있습니다

노드 x가 오른쪽 자식 노드인 경우: 이 경우에는 계속해서 부모 노드로 이동합니다.
노드 x가 왼쪽 자식 노드인 경우: 이 경우에는 현재 노드 x의 부모 노드가 바로 후계자가 됩니다.

def tree_successor(self, x):
        if x.right is not None:
            return self.tree_minimum(x.right)
        y = x.parent
        while y is not None and x == y.right:
            x = y
            y = y.parent
        return y

inorder_tree_walk()

BST의 모든 노드들이 키 값의 오름차순으로 출력해주는 함수입니다. BST의 중요한 특징 중 하나인 키의 순서적 정렬을 확인할 수 있는 방법입니다.

이진 탐색 트리를 중위 순회한 모든 노드의 키 값을 키 순서대로 출력합니다. 왼쪽 서브 트리부터 시작해 현재 노드의 값을 출력하고, 마지막으로 오른쪽 서브 트리를 방문하는 방식입니다.

함수의 작동 방식은 아래와 같습니다.

x가 None이 아닌 경우에만 실행됩니다.
왼쪽 서브 트리를 순회하기 위해 self.inorder_tree_walk(x.left)를 호출합니다. 왼쪽 서브 트리의 가장 왼쪽 노드까지 내려가게 되고, 그 노드부터 시작하여 순차적으로 값을 출력합니다.
다음으로 현재 노드의 값을 출력하고, 이어서 오른쪽 서브 트리를 순회하기 위해
self.inorder_tree_walk(x.right)를 호출합니다. 그 후, 오른쪽 서브트리를 중위 순회하여 그 노드들의 값을 출력합니다.

이러한 방식으로 중위 순회를 수행하면, BST의 모든 노드들이 키 값의 오름차 순으로 출력됩니다.

 def inorder_tree_walk(self, x):
        if x is not None:
            self.inorder_tree_walk(x.left)
            print(x.key, end=' ')
            self.inorder_tree_walk(x.right)

transplant()

이진 탐색 트리에서 노드를 이동시키는데에 사용됩니다. 주로, 후계자를 이동시킬때 사용됩니다.

코드의 동작은 아래와 같습니다.

먼저, 노드 u의 부모가 없는 경우(u.parent is None)에는 u가 루트 노드인 경우입니다. 이 경우에는 v를 새로운 루트로 설정합니다(self.root = v).
그렇지 않고 u가 부모의 왼쪽 자식인 경우(u == u.parent.left)에는 v를 u의 부모의 왼쪽 자식으로 설정합니다(u.parent.left = v).
나머지 경우에는 u가 부모의 오른쪽 자식인 경우입니다. 이 경우에는 v를 u의 부모의 오른쪽 자식으로 설정합니다(u.parent.right = v).
마지막으로, 만약 새로운 자식 노드 v가 None이 아니라면, 즉 u가 리프 노드가 아닌 경우에는 v의 부모를 u의 부모로 설정합니다(v.parent = u.parent).

def transplant(self, u, v):
        if u.parent is None:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if v is not None:
            v.parent = u.parent

tree_delete()

BST의 삭제 연산은 다음과 같이 삭제할 노드의 자식의 갯수에 따라 세 가지 경우로 나누어집니다.

💡 **Case 0**: 삭제할 노드가 자식이 없는 경우

Case 1: 삭제할 노드가 한 개의 자식을 가진 경우

Case 2: 삭제할 노드가 두 개의 자식을 가진 경우

각 케이스별로 설명해보겠습니다.

Case 0: 삭제할 노드가 자식이 없는 경우 삭제할 노드가 자식이 없는 경우, 직접 노드를 제거하면 됩니다.
Case 1: 삭제할 노드가 한 개의 자식을 가진 경우 자식이 하나인 노드를 삭제할 때는 해당 노드를 삭제하고 그 자식을 그 위치에 이동시키면 됩니다. 이를 수행하기 위해 다음과 같은 단계를 따릅니다:
1. 삭제할 노드 z의 부모 노드 y를 찾습니다.
2. 삭제할 노드 z의 자식 노드 x를 결정합니다. 자식이 하나인 경우에는 그 자식 노드가 x가 됩니다.
3. 부모 노드 y의 자식을 삭제할 노드 z의 자식 노드 x로 변경합니다. 이를 위해 부모 노드의 적절한 자식 포인터를 x로 설정합니다.
4. 삭제된 노드 z를 반환합니다.
Case 2: 삭제할 노드가 두 개의 자식을 가진 경우 삭제할 노드가 두개의 자식을 가지는 경우, 삭제하려는 노드의 후계자를 찾고, 그 값을 삭제하려는 노드에 복사합니다. 이후, 후계자의 오른쪽 자식이 존재한다면, 해당 자식을 후계자 부모의 왼쪽 자식으로 연결하고, 후계자가 자식이 없다면 그냥 후계자를 삭제한 것으로 처리합니다. 이는 위의 case0 과 case1 의 경우와 동일합니다.

def tree_delete(self, z):
    # 어떤 노드를 잘라내야 하는지 결정: z 또는 z의 후계자
    if z.left is None or z.right is None:
        y = z  # case 0 or 1
    else:
        y = self.tree_successor(z)  # case 2

    # x를 y의 NIL이 아닌 자식으로 설정하거나, y가 자식이 없으면 NIL로 설정
    if y.left is not None:
        x = y.left
    else:
        x = y.right

    # y가 트리에서 제거되며, p[y]와 x의 포인터를 조작함
    if x is not None:
        x.parent = y.parent

    if y.parent is None:
        self.root = x
    elif y == y.parent.left:
        y.parent.left = x
    else:
        y.parent.right = x

    # z의 후계자가 잘라낸 경우, 해당 데이터를 z로 복사함
    if y != z:
        z.key = y.key
        # 여기서 다른 위성 데이터도 필요한 경우 해당 데이터를 복사해야 합니다.
        
    return y

print_tree() , _print_tree_recursive

실습을 위해 tree를 출력하기 위한 함수를 아래와 같이 정의했습니다.

		def print_tree(self):
        self._print_tree_recursive(self.root, 0)

    def _print_tree_recursive(self, node, level):
        if node is None:
            return
        self._print_tree_recursive(node.right, level + 1)
        print('  ' * level + str(node.key))
        self._print_tree_recursive(node.left, level + 1)

BST Test

Initial BST (in-order traversal)

# test
if __name__ == "__main__":
    bst = BST()
    nodes = [56, 26, 200, 18, 28, 190, 213, 12, 24, 27]
    for key in nodes:
        bst.tree_insert(Node(key))

    print("Initial BST (in-order traversal):")
    bst.inorder_tree_walk(bst.root)
    print()  # 줄바꿈
    bst.print_tree()

현굥

다음 포스트

Binary Search Tree의 구현

algorithm

이진 탐색 트리 (Binary Search Tree, BST)

BST의 특징:

BST의 구현

Node

BST

BST Test

[algorithm] 이진탐색(Binary Search)

0개의 댓글