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

Python으로 정렬된 연결 리스트를 이진 검색 트리(BST)로 변환하는 방법

정렬된 연결 리스트(Linked List)가 주어졌을 때, 이를 이진 검색 트리(Binary Search Tree, BST)로 변환하는 문제를 살펴보겠습니다.

문제 정의

크기가 n인 정렬된 연결 리스트가 있다고 가정합니다. 다음 규칙에 따라 이진 검색 트리를 만들어야 합니다.

  • k = floor(n / 2) 번째로 작은 값을 찾아 루트(root)로 설정합니다.
  • k번째 노드보다 왼쪽에 있는 연결 리스트 부분으로 재귀적으로 왼쪽 서브트리를 구성합니다.
  • k번째 노드보다 오른쪽에 있는 연결 리스트 부분으로 재귀적으로 오른쪽 서브트리를 구성합니다.

예를 들어, 입력이 [2, 4, 5, 7, 10, 15]라면 출력되는 트리는 다음과 같습니다.

Python으로 정렬된 연결 리스트를 이진 검색 트리(BST)로 변환하는 방법

해결 접근 방법: 느린 포인터와 빠른 포인터(Slow & Fast Pointer)

이 문제는 투 포인터(Two Pointer) 기법을 사용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

  • 느린 포인터(slow)는 한 칸씩, 빠른 포인터(fast)는 두 칸씩 이동시킵니다.
  • 빠른 포인터가 끝에 도달하면, 느린 포인터는 자동으로 리스트의 중간 지점(k번째 노드)에 위치하게 됩니다.
  • 중간 노드를 루트로 삼고, 그 앞부분과 뒷부분을 각각 재귀적으로 처리하여 왼쪽·오른쪽 서브트리를 만듭니다.

알고리즘 단계

  1. solve() 메서드를 정의하고 노드(node)를 인자로 받습니다.
  2. 노드가 null이면 null을 반환합니다.
  3. 노드의 next가 null이면(노드가 하나뿐이면), 해당 값으로 새 트리 노드를 만들어 반환합니다.
  4. slow와 fast를 모두 node로 초기화하고, prev는 None으로 설정합니다.
  5. fast와 fast.next가 모두 null이 아닌 동안 반복합니다:
    • prev := slow
    • slow := slow.next
    • fast := fast.next.next
  6. 반복이 끝나면 prev.next를 None으로 설정하여 리스트를 두 부분으로 분리합니다.
  7. slow의 값으로 루트 노드를 생성합니다.
  8. 루트의 왼쪽 자식은 solve(node), 오른쪽 자식은 solve(slow.next)의 결과로 설정합니다.
  9. 루트를 반환합니다.

Python 구현 코드

class ListNode:
    def __init__(self, data, next = None):
        self.val = data
        self.next = next

class TreeNode:
    def __init__(self, data, left = None, right = None):
        self.data = data
        self.left = left
        self.right = right

def make_list(elements):
    head = ListNode(elements[0])
    for element in elements[1:]:
        ptr = head
        while ptr.next:
            ptr = ptr.next
        ptr.next = ListNode(element)
    return head

def print_tree(root):
    if root is not None:
        print_tree(root.left)
        print(root.data, end = ', ')
        print_tree(root.right)

class Solution:
    def solve(self, node):
        if not node:
            return None
        if not node.next:
            return TreeNode(node.val)
        slow = fast = node
        prev = None
        while fast and fast.next:
            prev = slow
            slow = slow.next
            fast = fast.next.next
        prev.next = None
        root = TreeNode(slow.val)
        root.left = self.solve(node)
        root.right = self.solve(slow.next)

        return root

ob = Solution()
head = make_list([2,4,5,7,10,15])
root = ob.solve(head)
print_tree(root)

입력

[2,4,5,7,10,15]

출력

2, 4, 5, 7, 10, 15,

코드 설명

make_list() 함수는 파이썬 리스트를 연결 리스트로 변환하는 유틸리티 함수입니다. 각 요소를 순회하며 ListNode 객체를 연결합니다.

print_tree() 함수는 중위 순회(In-order Traversal) 방식으로 트리를 출력합니다. BST의 특성상 중위 순회 결과는 항상 정렬된 순서로 나타나므로, 출력 결과가 원래 입력 리스트와 동일한 것을 확인할 수 있습니다. 이는 트리가 올바르게 구성되었음을 검증하는 좋은 방법입니다.

Solution.solve() 메서드가 핵심 로직입니다. 시간 복잡도는 각 재귀 호출마다 리스트를 절반으로 나누므로 O(n log n)이며, 공간 복잡도는 재귀 스택을 고려해 O(log n)입니다.

마무리

이처럼 느린 포인터와 빠른 포인터 기법을 활용하면 연결 리스트의 중간 노드를 O(n) 시간 안에 찾을 수 있으며, 이를 재귀적으로 활용해 균형 잡힌 이진 검색 트리를 손쉽게 구성할 수 있습니다. 정렬된 데이터를 트리 구조로 변환해야 하는 다양한 알고리즘 문제에서 유용하게 응용할 수 있는 패턴이니 꼭 기억해 두세요.