[자료구조] 이진 탐색 트리

이진 탐색 트리

왼쪽 트리에는 자신보다 작은 크기의 데이터를 가지는 노드들만,

오른쪽 트리에는 자신보다 큰 크기의 데이터를 가지는 노드들만 저장하는 이진트리이다.

 

따라서 데이터를 찾을 때 데이터가 현재 노드의 데이터보다 작다면 왼쪽으로, 크다면 오른쪽으로 향하면 된다.

---

완전 이진트리는 아닐 수도 있기 때문에 배열이나 리스트를 활용할 수는 없다.

 

따라서 노드 정보를 가질 수 있는 node 클래스를 만들어서 사용한다.

이 클래스는 데이터정보,부모노드정보,좌측자식노드정보,우측좌식노드정보를 가져야 한다.

 

그리고 좀 더 쉬운 관리를 위해

root노드 정보를 가지고 있는 tree클래스도 만들어준다.

---

이전에 배운 in-order순회대로 이진 탐색트리를 출력하면

데이터의 크기 순서대로 데이터가 출력될 것임을 짐작할 수 있다.

왼쪽 트리에는 작은 노드들이, 오른족 트리에는 큰 노드들이 저장되어 있기 때문이다.

---

이진 탐색 트리에 데이터를 삽입하려면

 

이진 탐색 트리의 특성대로 root에서부터 데이터를 비교해서 내려가면서 자리를 찾는다. (해당 노드보다 작으면 왼쪽 크면 오른쪽) 자리를 찾으면 해당 노드의 자식 노드에 새로운 데이터가 담긴 노드를 저장해주고, 새로운 데이터가 담긴 노드의 부모 노드는 해당 노드로 저장해준다.

 

최악의 경우 트리의 가장 깊은 곳에 데이터를 저장하므로,

트리의 높이가 h라고 할 때 삽입연산의 시간 복잡도는 O(h+1) = O(h)라고 할 수 있다.

 

탐색 역시 삽입과 비슷한 과정을 겪으므로 시간 복잡도는 O(h)이다.

---

이진 탐색 트리에서 데이터를 삭제하려면

 

먼저 해당 데이터를 가지고 있는 노드를 탐색해야 한다. 탐색을 마치고 대상 노드가 어떤 특성을 지니고 있는지에 따라 절차가 조금 달라진다.

 

1) 해당 노드가 leaf 노드일 경우에는 그냥 부모노드에 접근해서 해당 정보를 None으로 바꿔주면 된다.

2) 해당 노드가 leaf 노드가 아니고 자식을 하나만 가지고 있을 경우에는 부모 노드에 접근해서 해당 정보를 자식 정보로 바꿔주면 된다.

3) 해당 노드가 leaf 노드가 아니고 자식을 두개 가지고 있을 경우에는 조금 복잡하다. 해당 노드의 successor노드를 찾아주어야 한다. successor 노드란 해당 노드보다 큰 노드의 부분 트리 중 가장 작은 노드이다. successor 노드를 찾았다면 삭제 대상 노드의 데이터정보와 successor 노드의 데이터 정보를 바꿔준다. 이때 주의해야 할 점은 successor노드에게는 왼쪽 자식 노드는 절대 없지만(정의상 가장 작은 노드이기 때문에) 오른쪽 자식 노드는 있을 수 있다. 따라서 오른쪽 자식 노드가 None이 아닐 경우를 대비해서 해당 과정도 처리해주어야 한다.

 

참고로 삭제 역시 시간복잡도는 O(h)이다. (가장 오래 걸릴 것으로 보이는 삭제 대상 노드가 자식을 두 개 가지고 있을 경우도, 탐색하는 데에 O(h)만큼 걸리고, successor노드를 찾는데에 O(h)만큼 걸리고, 데이터를 바꾸는데 O(1)만큼 걸려 총 O(2h + 1) = O(h)만큼 걸리는 것을 알 수 있다.)

---

이진 탐색트리의 높이 h는 평균적으로 lg(n)이다. 최악의 경우 n이다.

따라서 삽입,탐색,삭제의 연산 역시 O(lg(n))라고 할 수도 있겠다.

 

다만 이진 탐색 트리에서 삽입, 삭제가 빈번하게 일어나면 이 형태가 깨지면서 균형 잡힌 형태(완전 이진트리의 형태)를 잃게 될 수 있다는 점은 기억하자.

 

---

이진 탐색 트리로는 딕셔너리나 세트도 구현이 가능한데,

이때 이진 탐색 트리의 특성상 이에 '순서'라는 특성을 부여할 수 있다.

 

앞서 보았듯이 이진 탐색 트리는 탐색,삭제,삽입 어떤 것에 있어서도 해시 테이블에 비해 시간 복잡도가 훨씬 비효율적이다. 하지만, '순서'를 부여할 수 있다는 특성이 있어 이를 위해 종종 활용되곤한다.