Computer >> 컴퓨터 >  >> 프로그래밍 >> Python

파이썬으로 이진 탐색 트리(BST)를 활용해 데이터를 정렬하는 방법

이진 탐색 트리(Binary Search Tree)를 이용해 정렬을 수행하려면 먼저 클래스를 정의하고, 그 안에 새로운 요소를 삽입하는 메서드와 중위 순회(inorder traversal)를 수행하는 메서드를 구현하면 됩니다.

이진 탐색 트리는 왼쪽 자식에는 부모보다 작은 값, 오른쪽 자식에는 부모보다 크거나 같은 값을 저장하는 자료구조입니다. 이러한 특성 덕분에 트리를 중위 순회(왼쪽 → 루트 → 오른쪽 순서)하면 항상 오름차순으로 정렬된 결과를 얻을 수 있습니다.

아래는 전체 예제 코드입니다.

예제 코드

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

    def insert_elem(self, node):
        if self.key > node.key:
            if self.left is None:
                self.left = node
                node.parent = self
            else:
                self.left.insert_elem(node)
        elif self.key <= node.key:
            if self.right is None:
                self.right = node
                node.parent = self
            else:
                self.right.insert_elem(node)

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


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

    def inorder_traversal(self):
        if self.root is not None:
            self.root.inorder_traversal()

    def add_val(self, key):
        new_node = BinSearchTreeNode(key)
        if self.root is None:
            self.root = new_node
        else:
            self.root.insert_elem(new_node)


my_instance = BinSearchTree()

my_list = input('Enter the list of numbers... ').split()
my_list = [int(x) for x in my_list]
for x in my_list:
    my_instance.add_val(x)
print('Sorted list: ')
print(my_instance.inorder_traversal())

실행 결과

Enter the list of numbers... 67 54 89 0 11 34 99
Sorted list:
0 11 34 54 67 89 99

코드 설명

  • 필요한 속성들을 가진 BinSearchTreeNode 클래스를 생성합니다.

  • __init__ 생성자는 노드의 값을 저장하는 key와 함께 left, right, parent 포인터를 None으로 초기화합니다.

  • insert_elem 메서드는 새 노드를 삽입할 때 기존 노드와 값을 비교하여, 더 작으면 왼쪽 하위 트리로, 크거나 같으면 오른쪽 하위 트리로 재귀적으로 이동하며 적절한 위치를 찾아 연결합니다.

  • inorder_traversal 메서드는 왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리 순서로 재귀 호출하며 중위 순회를 수행합니다.

  • BinSearchTree 클래스는 트리 전체를 관리하는 역할을 하며, 초기 상태에서 루트 노드(root)를 None으로 설정합니다.

  • add_val 메서드는 새로운 노드 객체를 만들고, 루트가 비어 있으면 루트로 지정하고, 그렇지 않으면 insert_elem을 호출해 트리에 추가합니다.

  • 사용자로부터 공백으로 구분된 숫자 목록을 입력받은 후, 각 숫자를 트리에 차례대로 삽입합니다.

  • 마지막으로 중위 순회를 실행하면 정렬된 결과가 콘솔에 출력됩니다.

참고 사항

이 방식의 시간 복잡도는 평균적으로 O(n log n)이지만, 이미 정렬된 데이터가 입력되면 트리가 한쪽으로 치우쳐(skew) 최악의 경우 O(n²)까지 느려질 수 있습니다. 균형 잡힌 트리가 필요하다면 AVL 트리나 레드-블랙 트리 같은 자가 균형 이진 탐색 트리를 고려하는 것이 좋습니다.