이진 탐색 트리

지침

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

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

배열 [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

출처

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