Searching

특정 노드의 검색

탐색 트리가 좋은 성능을 유지하려면 트리가 한쪽 방향으로 기울어지지 않도록 해야 한다.
다음 그림처럼 탐색 트리의 각 말단 노드에서 루트까지의 높이가 모두 같거나 오직 1만큼만 차이가 난다면 최악의 경우에도 비교 횟수가 log2(n)을 넘지 않는다. 이러한 트리를 균형 탐색 트리라 한다.
균형탐색 트리의 대표적인 예로는 이진 트리인 AVL트리와 3진트리인 2-3트리가 있다.

AVL트리는 균형 이진 탐색 트리로서 다음과 같이 재귀적으로 정의된다.
- 트리의 높이는 각 단말노드로부터 루트 노드까지의 노드 수 중에 가장 긴 것을 가리킨다고 하자.
- 이진 탐색 트리의 조건을 만족하면서 모든 노드에서 그 노드의 왼쪽 서브트리와 오른쪽 서브트리의 높이 차이가 1보다 크지 않으면 된다.
AVL트리는 노드가 삽입/삭제될ㅤ때마다 트리가 균형을 이루도록 조정해주어야 한다. 이를 위해 각 노드에는 균형치(balance factor)를 부여한다. 균형치는 왼쪽 서브트리의 높이에서 오른쪽 서브트리의 높이를 뺀 값이다.
<균형치가 부여된 AVL트리의 예>

먼저 이진 탐색 트리에 노드를 삽입할 때처럼 해당 노드를 삽입하고 균형치를 조정해준다.
균형치가 -1에서 1사이의 값을 가지면 끝낸다.
균형치가 -1보다 작아지거나 1보다 커지면 균형이 깨진 것이다. 이ㅤ때는 균형치가 -2나 2가 되는 노드들 중에서 형재 삽입된 노드로부터 가장 가까운 노드에서부터 하위 노드들을 위치를 변형하여 균형을 이루도록 해준다.

그림을 마우스로 클릭하세요

2-3트리는 자식 노드를 3개까지 가질 수 있는 3진 트리로서 다음과 같이 정의된다.
1. 각 노드는 2노드 또는 3노드이다. 2-노드는 1개의 데이터 값을 가지며 3-노드는 2개의 데이터 값을 가진다.
2. 2-노드는 왼쪽 서브트리와 가운데 서브트리를 가지며 왼쪽 데이터값을 가진다. 왼쪽 서브트리의 모든 노드는 왼쪽 데이터 값보다 작은 값을 가진다. 왼쪽 서브트리의 모든 노드는 왼쪽 데이터 값보다 작은 값을 가지며, 가운데 서브트리의 모든 노드는 왼쪽 데이터 값보다 큰 값을 가진다.
3. 3-노드는 왼쪽 서브트리, 가운데 서브트리, 오른쪽 서브트리를 가지며 왼쪽 데이터 값과 오른쪽 데이터 값을 가진다. 왼쪽 서브트리의 모든 노드는 왼쪽 데이터 값보다 작은 값을 가진다. 가운데 서브트리의 모든 노드는 왼쪽 데이터 값보다는 큰 값을 가지며, 오른쪽 데이터 값보다는 작은 값을 가진다. 오른쪽 서브트리의 모든 노드는 오른쪽 데이터 값보다 큰 값을 가진다.
4. 모든 단말 노드들은 같은 레벨에 놓인다.

먼저 새로운 항목이 삽입될 노드를 찾는다.
찾아진 노드가 2-노드인 경우 그노드의 왼쪽 데이타 값과 삽입할 값을 비교하여 왼쪽 데이터 값이 작으면 오른쪽 데이터 위치에 그 값을 삽입한다.
<삽입전>

<삽입후>
왼쪽 데이터 값이 더 크면 오른쪽으로 옮기고 빈 자리에 삽입한다.
<삽입전>

<삽입후>
찾아진 노드가 3-노드인 경우는 기존 노드를 분리하여 새로운 노드로 만들어준다. 이때 삽입할 항목을 중심으로 하여 이웃한 두값들을 비교하여 가장 작은 값은 그대로 두고, 중간 값은 상위노드로, 가장 큰 값은 새로운 노드에 삽입한다.
<삽입전>

<삽입후>
기존 노드를 분리할 때 상위노드도 3-노드인 경우는 더이상 분리되지 않을 때까지 상위 노드를 따라가면서 재귀적으로 분리한다.

먼저 삭제할 항목을 찾는다.
찾아진 노드가 3-노드인 경우는 왼쪽 데이타인지 오른쪽 데이타인지를 검사한다. 오른쪽 데이타인 경우는 그대로 삭제하고, 왼쪽 데이타인 경우는 삭제후 쉬프트한다.
<삭제전>

<삭제후>
찾아진 노드가 2-노드인 경우는 삭제후 노드에 데이타가 남지 않으므로 2-3트리의 성절이 깨진다. 이런 경우는 이웃한 노드에서 데이타를 빌려와야 한다. 이웃한 노드에 3-노드인 경우는 한 항목을 빌려와서 왼쪽 데이타로 한다.
<삭제전>

<삭제후>
찾아진 노드가 2-노드이고 이웃한 노드도 2-노드인 경우는 두개의 노드를 병합한다.
<삭제전>

<삭제후>
삭제할 노드와 이웃한 노드, 그리고 상위 노드가 모두 2-노드인 경우는 3개의 노드를 병합한다.
<삭제전>

<삭제후>