이진 탐색 트리

지침

이진 트리에 숫자를 삽입하고 검색해요.

정렬된 데이터를 표현해야 할 때, 배열은 좋은 자료 구조가 아니에요.

예를 들어 배열 [1, 3, 4, 5]가 있고, 여기에 2를 추가해서 [1, 3, 4, 5, 2]가 되었다고 해봐요. 이제 전체 배열을 다시 정렬해야 해요! 우리가 해야 할 일은 새 항목을 위해 [1, nil, 3, 4, 5]처럼 자리만 만들고, 그 자리에 항목을 넣는 것뿐이라는 걸 깨닫으면 더 나아질 수 있어요. 하지만 그래도 많은 원소를 한 칸씩 뒤로 밀어야 해요.

그런데 이진 탐색 트리는 정렬된 데이터를 훨씬 더 효율적으로 다룰 수 있어요.

이진 탐색 트리는 연결된 노드들로 이루어져 있어요. 각 노드에는 데이터 한 조각(예: 숫자 3), left라는 변수, right라는 변수가 들어 있어요. left와 right 변수는 nil 또는 다른 노드를 가리켜요. 이 다른 노드들 아래에도 다시 다른 노드들이 있기 때문에, left와 right 변수가 서브트리를 가리킨다고 말해요. 왼쪽 서브트리의 모든 데이터는 현재 노드의 데이터보다 작거나 같고, 오른쪽 서브트리의 모든 데이터는 현재 노드의 데이터보다 커요.

예를 들어, 데이터 4를 담은 노드가 있고 데이터 2를 추가하면, 트리는 이렇게 돼요:

      4
     /
    2

그다음 6을 추가하면 이렇게 돼요:

      4
     / \
    2   6

그다음 3을 추가하면 이렇게 돼요

       4
     /   \
    2     6
     \
      3

그리고 1, 5, 7을 추가하면 이렇게 돼요

          4
        /   \
       /     \
      2       6
     / \     / \
    1   3   5   7

크레딧

이미지는 Till Tantau가 만든 PGF/TikZ를 사용해 habere-et-dispertire가 만들었어요.