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

이진 탐색 트리는 부모 노드 기준 작은 키는 좌측 자식 노드로, 큰 키는 우측 자식 노드로 유지하는 트리이다. 이러한 자료 구조는 데이터 탐색 시 노드를 이동하면서 재귀적으로 탐색 가짓수를 1/2로 줄여나가며 찾는다.

그러나 이진 탐색 트리는 키의 삽입 순서에 따라 트리의 균형이 달라지기 때문에 트리의 균형을 예측하기가 어렵다는 단점이 있다.

 

---

1. 이진 탐색 트리 삽입

부모 노드보다 작으면 좌측 자식 노드로, 부모 노드보다 크면 우측 자식 노드로 배치한다.

 

따라서 부모 노드 기준 좌측 끝에 있는 노드는 트리에서 가장 작은 키가, 부모 노드 기준 우측 끝에 있는 노드는 트리에서 가장 큰 키가 된다.

 

 

---

2. 이진 탐색 트리 삭제

노드를 삭제 시에도 이진 탐색 트리의 구조를 유지해야 하기 때문에 특정한 규칙에 의해 삭제하는 방식을 택한다.

 

예시로 삭제할 키가 12인 경우, 삭제되는 키 대신 그 자리를 채워줄 키가 필요하다. 그 키는 삭제할 키 기준 좌측 서브 트리에서 가장 큰 키(10) 이거나, 우측 서브 트리에서 가장 작은 키(13) 이다. 삭제할 노드 기준 자식 노드가 존재하지 않을 때 까지 반복해서 키를 swap 한다.

 

 

---

3. 이진 탐색 트리 순회

이진 트리의 순회와 동일하나, 값의 크기를 기준으로 내림차순 방문하고 싶다면 좌측 중위 순회를 하면 되고, 오름차순으로 방문하고 싶다면 중위 순회를 하면 된다. 

 

1) 좌측 중위 순회

void inOrder(Node parent) {
    inOrder(parent.left);
    visit();
    inOrder(parent.right);
}

---

2) 우측 중위 순회

void inOrder(Node parent) {
    inOrder(parent.right);
    visit();
    inOrder(parent.left);
}

 

---

참조

https://www.codelatte.io/courses/java_data_structure

자바 자료구조 강의 - 코드라떼