[알고리즘] BST와 링크드리스트로 이해하는 "참조(Reference)"의 원리

코딩테스트 합격자 되기(파이썬) 책의 '이진 탐색 트리 구현' 문제를 풀면서, =이 단순한 대입이 아니라 항상 "가리킴(참조)"이라는 걸 BST와 링크드리스트 두 자료구조로 비교하며 정리했다.

---

1. =은 항상 "가리킴(참조)"이다

숫자(int)와 객체(Node)는 =의 동작 원리가 똑같지만 결과가 다르게 보인다.

a = 5
b = a
a = 10
print(b)  # 5 ← 안 바뀜

숫자는 내부를 수정할 수 없어서 a = 10을 하면 a가 새로운 값을 가리키도록 바뀔 뿐, b에는 영향이 없다. 반면 객체는 내부를 수정할 수 있어서, 같은 객체를 가리키는 두 변수 중 하나로 내부를 바꾸면 다른 변수에도 그대로 반영된다.

curr = self.root          # curr이 self.root와 같은 객체를 가리킴
curr.left = Node(3)       # 그 객체의 내부를 수정
# self.root와 curr이 같은 객체를 가리키므로
# self.root.left도 자동으로 Node(3)이 된다

curr = curr.left도 같은 원리다. curr이 가리키던 노드의 left 필드가 가리키는 객체로 curr의 화살표가 이동하는 것이며, 그 필드가 None이면 curr도 None을 가리키게 된다. 이 None은 어딘가에서 새로 대입된 게 아니라, 노드를 생성할 때 left/right를 처음부터 None으로 초기화해 둔 값을 그대로 가져오는 것이다.

앞으로 =이 보이면 "왼쪽이 오른쪽을 가리킨다"로만 생각하면 된다. 숫자가 복사처럼 느껴졌던 건 단지 내부를 못 바꾸기 때문이었을 뿐, 동작 원리는 항상 같다.

---

2. 이진 탐색 트리(BST) 구현

BST 핵심 코드

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

    def insert(self, key):
        if not self.root:
            self.root = Node(key)
        else:
            curr = self.root
            while True:
                if key < curr.val:
                    if curr.left:
                        curr = curr.left
                    else:
                        curr.left = Node(key)
                        break
                else:
                    if curr.right:
                        curr = curr.right
                    else:
                        curr.right = Node(key)
                        break

    def search(self, key):
        curr = self.root
        while curr and curr.val != key:
            if key < curr.val:
                curr = curr.left
            else:
                curr = curr.right
        return curr

while curr and curr.val != key에서 curr 검사가 필요한 이유

curr이 None인 상태에서 curr.val에 접근하면 에러가 난다. and는 단락 평가(short-circuit)를 하기 때문에, 앞 조건인 curr이 False(=None)면 뒤의 curr.val != key는 아예 확인하지 않고 즉시 반복을 멈춘다. 이 덕분에 없는 노드에 접근하는 에러 없이 안전하게 종료할 수 있다.

curr = None → False → while 즉시 종료, .val 접근 자체를 안 함

트리가 채워지는 원리: 화살표의 연결

insert가 하는 일은 결국 "어디에 연결할지 while 루프로 찾기 → curr.left/right = Node(key)로 화살표 하나 연결하기" 단 두 단계다.

insert(5):  self.root ──→ [5]
insert(3):  self.root ──→ [5, left=──→[3]]
insert(8):  self.root ──→ [5, left=──→[3], right=──→[8]]
insert(4):  Node(3).right ──→ Node(4)   (4 > 3 이므로 오른쪽에 연결)

self.root 하나만 알면 화살표를 타고 트리 전체에 접근할 수 있다.

삽입 규칙이 곧 탐색 규칙이 되는 이유

삽입할 때: 작으면 왼쪽, 크면 오른쪽 → 규칙대로 저장
탐색할 때: 작으면 왼쪽, 크면 오른쪽 → 같은 규칙으로 추적

이 규칙 덕분에 모든 노드를 확인할 필요 없이, 비교할 때마다 절반(또는 그 이하)의 후보를 제거하면서 탐색할 수 있다. 일반 리스트는 최악의 경우 N개를 전부 확인해야 하지만, 균형 잡힌 BST는 트리의 높이(log N)만큼만 비교하면 된다.

탐색 대상이 일반 리스트면:  5→3→8→4→2→1→7→10 (전부 확인)
탐색 대상이 BST면:          5→8→7→None (3번만 확인하고 "없음" 판단)

시간복잡도: 왜 O(N²)인가

insert를 N번 호출하는데, 한 번의 insert가 몇 번 비교하느냐는 트리 모양에 달려 있다.

• 균형 잡힌 트리: 한 번 삽입할 때 트리 높이(log N)만큼만 비교 → 전체 O(N log N)
• 한쪽으로 치우친 트리 (예: 정렬된 리스트를 그대로 삽입): N번째 삽입이 N-1번 비교 → 전체 0+1+2+...+(N-1) = O(N²)

1
 \
  2
   \
    3     ← 입력이 이미 정렬돼 있으면 트리가 일직선이 됨
     \
      4

책에서 O(N²)으로 표기한 것은 최악의 경우(이미 정렬된 입력) 를 기준으로 한 것이다.

클래스 없이 풀기: set 활용

이 문제가 실제로 필요로 하는 건 "이 값이 있냐 없냐"뿐이다. 파이썬의 set은 해시(hash)를 이용해 평균 O(1) 으로 존재 여부를 확인할 수 있어서, BST를 직접 구현하지 않고도 같은 결과를 더 빠르고 짧게 얻을 수 있다.

def solution(lst, search_lst):
    s = set(lst)
    return [val in s for val in search_lst]

자료구조 탐색 속도 비고

리스트	O(N)	처음부터 하나씩 확인
BST	O(log N) ~ O(N)	트리 모양에 따라 다름
set	O(1)	해시로 즉시 위치 파악

코딩테스트 실전에서는 set/dict를 쓰는 게 유리하지만, BST를 직접 구현해보는 건 클래스·참조·트리 구조를 이해하는 데 의미가 있다.

---

3. 링크드 리스트: 화살표 하나로 줄어든 BST

BST가 한 노드에서 left, right 두 방향으로 뻗어나가는 구조라면, 링크드 리스트는 next 하나만 가리키는 일직선 구조다. 구현 원리는 완전히 동일하다.

링크드 리스트:                BST:
[1] ──→ [2] ──→ [3]              [5]
화살표 1개 (next)              /    \
                              [3]   [8]
                          화살표 2개 (left, right)

구현

class LinkedList:
    def __init__(self):
        self.head = None

    def append(self, val):
        new_node = Node(val)
        if not self.head:
            self.head = new_node
            return
        curr = self.head
        while curr.next:
            curr = curr.next
        curr.next = new_node

    def prepend(self, val):
        new_node = Node(val)
        new_node.next = self.head
        self.head = new_node

    def delete(self, val):
        if not self.head:
            return
        if self.head.val == val:
            self.head = self.head.next
            return
        curr = self.head
        while curr.next:
            if curr.next.val == val:
                curr.next = curr.next.next  # 건너뜀
                return
            curr = curr.next

    def search(self, key):
        curr = self.head
        while curr:
            if curr.val == key:
                return True
            curr = curr.next
        return False

BST vs 링크드리스트 대응 관계

BST 링크드리스트

입구	self.root	self.head
화살표	left, right	next
이동	curr = curr.left/right	curr = curr.next
삽입 위치	값 크기 규칙에 따라	맨 뒤(append) 또는 맨 앞(prepend)
탐색	규칙 따라 절반씩 제거	처음부터 끝까지 순차 탐색
탐색 시간복잡도	O(log N) ~ O(N)	O(N)

delete가 "건너뛰기"로 동작하는 원리

삭제는 노드를 메모리에서 직접 지우는 게 아니라, 이전 노드의 next가 삭제 대상을 건너뛰고 그다음 노드를 가리키도록 화살표를 재연결하는 것이다.

삭제 전: [0] ──→ [1] ──→ [2] ──→ [3]
                          ↑ 삭제 대상

curr.next = curr.next.next  →  [2]를 가리키던 화살표를 [3]으로 교체

삭제 후: [0] ──→ [1] ──→ [3]
                       ↑ [2] 건너뜀 (아무도 안 가리키므로 사실상 제거됨)

---

4. 정리

• =은 숫자든 객체든 항상 "오른쪽이 가리키는 것을 왼쪽도 가리킨다"는 의미다. 객체는 내부를 수정할 수 있어서 같은 객체를 가리키는 다른 변수에도 변경이 그대로 반영된다.
• BST는 삽입 규칙(작으면 왼쪽, 크면 오른쪽)이 곧 탐색 규칙이 되기 때문에 빠른 탐색이 가능하지만, 입력이 정렬되어 있으면 트리가 한쪽으로 치우쳐 O(N²)까지 느려질 수 있다.
• 링크드리스트는 BST에서 화살표가 next 하나로 줄어든 구조로, 원리는 동일하다.
• 코딩테스트에서 "존재 여부 확인"이 목적이라면 BST를 직접 구현하기보다 파이썬의 set/dict를 활용하는 게 더 효율적이다.