자료구조 - 이진탐색트리

이진탐색트리

이진트리의 노드는 왼쪽과 오른쪽으로 자식을 가집니다. 이러한 이진트리 중에서 탐색을 위해

고안 된 트리가 바로 이진탐색트리입니다.

● 이진탐색트리의 조건

이진 탐색트리는 다음과 같은 조건을 가집니다.

1. 임의의 노드 N에 대하여, 왼쪽 하위에 있는 노드는 N 보다 값이 작고, 오른쪽 하위 노드는

   N 보다 값이 커야 한다.

2. 임의의 노드 N 의 왼쪽 하위 트리와 오른쪽 하위 트리 모두 이진 탐색트리여야 한다.

이진탐색트리의 모양 예시

이러한 이진 탐색트리를 중위순회 하게 될 경우 데이터가 정렬된 결과를 보입니다.

트리의 순회에 대해선 저번 글을 참조해주세요~

● 이진 탐색트리의 탐색

앞에서 설명한 대로, 이진 탐색 트리의 목적은 바로 탐색에 있습니다.

탐색하고자 하는 값을 찾을 때, 루트부터 시작해서 그 값을 비교합니다.

만약에 찾고자 하는 값이 루트보다 크다면 오른쪽, 작다면 왼쪽을 다시 탐색하면 됩니다.

이 과정은 재귀적으로 풀어 낼 수 있습니다.

이러한 탐색이 빠른 이유는 탐색 과정을 으로 줄일 수 있기 때문입니다.

이진탐색 트리 안에 1000개의 데이터가 들어 있을 경우 아무리 오래 걸려도 10번 이내의

비교과정으로 원하는 값을 탐색 할 수 있을 것입니다.

찾는 데이터가 왼쪽인지 오른쪽인지 선택하는 과정에서 매번 절반의 데이터를 걸러낼 수 있기 때문이죠.

이러한 탐색과정을 의사코드로 나타낸다면 다음과 같습니다.

Nptr Search(Nptr node, Key) {     if(NULL == node )        printf("찾지 못함“);   // 예외상황       else if(node->data > Key)        Search(node->Lchild, Key);     else if(node->data < Key)        Search(node->Rchild, Key);     else                       // node->data 와 Key 값이 같다면        reutrn node;    }

● 이진 탐색트리의 삽입

이진 탐색 트리의 삽입 과정은 탐색과정과 유사합니다. 입력 될 데이터의 위치가 어느 곳이 될지

자기 자리를 탐색하는 과정이기 때문이죠.

이진 탐색트리의 삽입 과정 역시 재귀적으로 풀어 낼 수 있지만, 비효율적이므로,

반복문으로 나타내 보았습니다. 재귀적으로 구현하는 방식은 각자 한번 생각해 보도록 합시다.

다음은 반복문을 사용해서 구현한 이진 탐색트리의 삽입 의사코드입니다.

void Insert(Nptr node, Key) {     Nptr NewNode = new NODE;     NewNode->data = Key;     if (NULL == node) // 루트가 비었다면,      {         node = NewNode; // 새로 삽입한 노드를 루트노드로 지정한다.         return;     }          while (true)     {         if (node->data > Key) // 입력 데이터가 현재 노드의 데이터보다 작다면          {             if (NULL != node->Lchild)                node = node->Lchild; // 왼쪽 자식으로 내려간다.                            else              {                 node->Lchild = NewNode; // 더 이상 내려갈 곳이 없다면 그 자리가 새로운 노드의 자리다.                return;              }                     }                else if (node->data < Key)// 입력 데이터가 현재 노드의 데이터보다 크다면         {            if (NULL != node->Rchild)                node = node->Rchild; // 오른쪽 자식으로 내려간다.                            else              {                 node->Rchild = NewNode; // 더 이상 내려갈 곳이 없다면 그 자리가 새로운 노드의 자리다.                return;              }         }            } }

● 이진 탐색트리의 삭제

이진 탐색트리의 삭제작업은 조금 까다롭습니다.

우선 삭제 할 노드를 탐색하는 과정이 끝나면, 다음과 같은 세 가지 경우로 나뉘게 됩니다.

1. 삭제할 노드가 단말노드인 경우.

2. 삭제할 노드가 자식노드를 한 개 가진 경우(왼쪽, 또는 오른쪽).

3. 삭제할 노드가 2개의 자식을 가진 경우.

 

위와 그림으로 예를 들어보겠습니다.

A 노드 또는 K 노드를 삭제한다고 했을 경우 이는 삭제할 노드가 단말노드인 경우에 해당합니다.

이때, A 또는 K 노드를 삭제하고, 그 부모노드가 해당 노드로의 연결을 끊으면 됩니다.

자식이 하나있는 노드의 경우를 봅시다.

만약 H 노드를 삭제한다고 했을 때, H 노드는 삭제하고, H 노드의 오른쪽 자식인 K 노드를 L 노드의

왼쪽 자식으로 연결지어주면 해결됩니다. 이렇게 하더라도, K 노드가 L 노드보다 순서가 앞이므로 왼쪽에

연결하는 것에 문제가 없습니다.

자식이 하나있는 F 노드가 삭제된다면, G 노드의 왼쪽 자식으로 B 노드를 연결합니다.

마찬가지로 중위 순회 결과가 A->B->D->F->G 순에서 A->B->D->G 로 변경되므로, 중간에 F만 쏙

빠지게 되는 결과입니다. 이는 중위순회 순서에 벗어나지 않으므로 문제가 없습니다.

즉 자식이 1개 있는 경우, 삭제할 노드가 부모의 왼쪽자식인지 오른쪽자식인지에 따라서 그 자리에

자기의 자식노드를 연결해주면 해결됩니다.

하지만 자식이 2개있는 노드를 삭제할 경우는 조금 신경 쓸 필요가 있습니다.

만약 B 노드를 삭제하려고 할 경우, B 자리에 누가 와야 할까요?

노드의 값의 크기 순서를 해치지 않기 위해서, 중위 순회의 결과가 어긋나지 않는 값이 와야 할 것입니다.

중위 순회 해 보면 A->B->D->F->G->H->K->L 순입니다. 따라서 B 가 삭제된 자리는 A or D 가

적절 할 것입니다.

이때 A 는 B 의 중위 선행자(In-Order Predecessor),

D는 B의 중위 후속자(In-Order Successor) 라고 부릅니다.

따라서 A or D 가 B의 자리로 값을 복사하고, 복사한 노드(A or D)를 삭제하면 될 것입니다.

그렇다면 G 노드가 삭제될 경우를 생각해 봅시다.

G가 삭제된 후에 누가 그 자리를 대신 해야 할까요?

G 의 중위 후속자를 생각해 봅시다.

H 노드가 중위 후속자입니다. 따라서 G 자리에 H 값이 복사되고 나면 원래 H 노드는 삭제되어야 할 텐데, H 노드는 자식을 1개 가지고 있는 경우입니다.

따라서 H 노드를 삭제할 때 자식이 1개있는 경우로 처리를 해야 할 것입니다

이러한 중위 후속자의 특징은, 자식이 없거나 1개라는 것입니다.

중위 순회의 특성 상 중위 후속자의 자식은 2개가 될 수 없습니다.

그 이유는 중위 후속자는 해당 노드의 오른쪽 자식으로 가서, 왼쪽 자식이 없을 때 까지 도달했을 때가

바로 중위 후속자 이기 때문입니다.

● 이진 탐색트리의 효율

이진 탐색트리의 탐색 효율은    이라고 볼 수 있습니다.

하지만 이것은 트리가 매우 균형이 잘 잡혀 있을 때의 이야기입니다.

처음 삽입되는 데이터를 루트로 삼는 이진 탐색트리의 특성상 첫 루트값이 한쪽에 치우쳐 진 경우,

트리가 균형을 잡기 어려워집니다.

균형적	불균형

최악의 경우 n 개의 데이터가 한쪽으로 매달려 있는 경우도 발생 할 수 있습니다.

이렇게 한쪽으로 쏠린 채로 진행하는 경우를 편향 이진트리 라고 하며, 동일한 구성요소로 트리가

채워져 있음에도 균형에 따라서 탐색의 효율이 달라집니다.

최악의 경우, 이진 탐색트리의 탐색 효율은 O(N) 일 것이며, 평균적으로 O(logN) 의 효율을 보일 것입니다.

이러한 불균형 문제를 해결하기 위해 고안된 이진 탐색트리가 바로 AVL 트리, 레드블랙 트리입니다.

     

- by Raimondo