이진 탐색 트리

이진탐색 트리는 이진트리의 일종이다.

이진 탐색트리는 저장 할 때 큐칙이 있다.

• 아진 탐색 트리의 노드에 저장된 키는 유일하다.
• 루트 노드의 키가 왼쪽 서브트리를 구성하는 어떠한 노드의 키보다 크다.
• 루트 노드의 키가 오른쪽 서브트리를 구성하는 어떠한 노드의 키보다 작다.

이런 식으로 자료 구조를 설정한다고 생각하면 값을 탐색 할 때, 길을 잃을 일이 없을 것이다.

왼쪽 자식 노드의 키 < 부모 노드의 키 < 오른쪽 자식 노드의 키

이진 탐색트리의 추상 자료형

이진 탐색 트리와 크게 다르지 않다.

• void BSTMakeAndInit(BTreeNode **pRoot)
• BSTData BSTGetNodeData(BTreeNode *bst);
• void BSTInsert(BTreeNode **pRoot, BSTData data);
• BTreeNode *BSTSearch(BTreeNode *bst, BSTData target);

이진 탐색 트리의 삽입과 탐색

삽입 할때는 기존의 규칙에 맞게 루트 보다 크면 오른쪽 작으면 왼쪽으로 이동하며, 비교 대상이 없을 떄 까지 내려간다. 그리고 그 비교대상이 없는 위치가 새 데이터가 저장될 위치이다.

탐색도 같다. target에 기준에 맞는 값을 찾을 때까지 기준에 맟춰 위치를 이동시킨다.

target == 11

11 > 10 → 오른쪽

11 < 13 → 왼쪽

이진 트리의 삭제

 

이진트리의 삭제의 경우 3가지 상황이 있다.

• 삭제 노드가 자식 노드가 없는 경우
• 삭제 노드가 1개의 자식노드를 갖는 경우
• 삭제 노드가 2개의 자식 노드를 갖는 경우

삭제 노드가 자식 노드가 없는 경우에는 그냥 삭제 하면된다.

삭제 노드가 1개의 자식 노드를 갖는 경우

삭제 노드의 자식 노드가 삭제 노드를 대체 하면된다.

마지막 경우는 어떻게 삭제 노드의 자리를 대체 해야할까에 대한 많은 생각을 필요로 한다.

이 경우 2가지 방법이 있는데.

• 왼쪽 자식 노드중 가장 작은 (큰)을 갖는 데이터로 대체한다.
• 오른쪽 자식 노드중 가장 작은 데이터로 대체 한다.

2번째 방법으로 예시를 들어본다.

삭제 노드인 13의 오른쪽 노드중 가장 작은 값은 15이다.

15의 값으로 13의 위치를 대신해보면. 이진 탐색트리의 조건을 만족한다.

위의 예시처럼 진행하기 위해서는 3가지 단계를 밟아야 한다.

• 단계 1 → 삭제할 노드를 대체할 노드를 찾는다
• 단계 2 →대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
• 단계 3 → 대체할 노드의 부모 노드와 자식 노드를 연결한다.

삭제할 노드를 찾는 과정

// cNode는 삭제할 노드를 가르킨다.
// pNode는 삭제할 노드의 부모노드를 가르킨다.
while (cNode != NULL && GetData(cNode) != target)
    {
        pNode = cNode;
        if (GetData(cNode) > target)
        {
            cNode = GetLeftSubTree(cNode);
        }
        else
            cNode = GetRightSubTree(cNode);
    }

현재 노드가 원하는 값이 아닐때 까지 반복문을 실행 시킨다.

단계1

// mNode는 대체할 노드를 가르킨다.
// mpNode는 대체할 노드의 부모노드를 가르킨다.
BTreeNode *mNode = GetRightSubTree(dNode);
BTreeNode *mpNode;
int delData;

while (GetLeftSubTree(mNode) != NULL)
{
			mpNode = mNode;
			mNode = GetLeftSubTree(mNode);
}

위의 예시에서 보면 mNode는 15 mpNode는 13을 가르킨다.

단계2

//dNode는 삭제할 노드를 가르킨다.
delData = GetData(dNode);
SetData(dNode, GetData(mNode));

단계3

if (GetLeftSubTree(mpNode) == mNode)
         ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
else
         ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

자식 노드를 연결한다.

위의 경우는else에 해당 한다.

ChangeRightSubTree(mpNode, GetRightSubTree(mNode));

mpNode(13) GetRightSubTree(mNode)(16)을 연결한다.