이진 탐색 트리

지침

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

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

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