이진 탐색 트리(BST: Binary Search Tree)

• 특징
  

각각의 노드는 고유한 키값이 존재

각 키값은 중복될 수 없다!

자식 노드는 최대 2개 까지

부모보다 작은 노드는 왼쪽에, 큰 노드는 오른쪽에 위치한다

탐색은 항상 최상단 루트(Root)부터

• 삽입

새 노드의 위치를 찾기 위해서 루트(Root)부터 탐색한다.

탐색한 노드보다 새 노드가 작으면 왼쪽, 크면 오른쪽으로 계속 탐색

다음 탐색 위치가 비어있다면, 그 위치에 새 노드 삽입

삽입 종료

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트 생성

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

 

        NODE* parent = m_root;        //부모 노드

        NODE* node = m_root->Right;   //현재 탐색 노드    

 

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

 

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //새 노드 생성

        node = new NODE(key);

 

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

 

}

• 삭제
  

삭제는 몇가지 종류로 나뉜다.

01. 자식이 없는 노드 삭제

02. 자식이 한쪽만 있는 노드 삭제

03. 자식이 양쪽 다 있는 노드 삭제

• 자식이 없는 노드 삭제

가장 간단한 경우 이다.

그냥 삭제하면 된다.

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

• 자식이 한쪽만 있는 노드 삭제    

삭제할 노드의 자식을

삭제노드의 위치로 옯겨주고

노드를 삭제하면 된다.

//자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

• 자식이 양쪽 다 있는 노드 삭제

  
  

자식이 양쪽 다 있는 노드를 삭제할때

왼쪽에서 가장 큰 노드를 찾아 삭제노드 위치에 두는 방법

오른쪽에서 가장 작은 노드를 찾아 삭제노드 위치에 두는 방법등

여러 방법은 많지만, 아래의 방법은 왼쪽에서 가장 큰 노드를 찾는 방법이다.

왼쪽에서 가장 큰 노드는 오른쪽 자식 노드가 없기 때문에

고려하지 않아도 된다.

//자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

• 삭제 전체 코드

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

 

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;     //자식 노드

        NODE* deleteNode;               //삭제 노드

 

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

 

               //현재 노드를 부모 노드로

               parent = node;

 

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

       

        //삭제할 노드 저장

        deleteNode = node;

 

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

 

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

 

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

 

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

• 전체 코드

#pragma once

class BinarySearchTree

{

private:

        typedef struct _Node

        {

               _Node(int key)

               {

                       Key = key;

                       Left = NULL;

                       Right = NULL;

               }

 

               int Key;

               struct _Node *Left;

               struct _Node *Right;

        }NODE;

 

private:

        NODE *m_root;

 

public:

        BinarySearchTree();

        ~BinarySearchTree();

 

        void Insert(int);

        NODE* Search(int);

        void Delete(int);

        void Print();

        bool IsEmpty();

        void Clear();

private:

        void Preorder(NODE*);

        void PrintNode(NODE*);

        void Clear(NODE*);

};

#include "stdafx.h"

#include "BinarySearchTree.h"

 

 

BinarySearchTree::BinarySearchTree()

{

        //루트 생성(실질적인 루트가 아님)

        //m_root->Right가 진짜 루트

        m_root = new NODE(-1);  

}

 

 

BinarySearchTree::~BinarySearchTree()

{

        Clear();

 

        delete m_root;

        m_root = NULL;

}

 

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트에 입력

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

 

        NODE* parent = m_root;

        NODE* node = m_root->Right;

 

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

 

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //새 노드 생성

        node = new NODE(key);

 

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

 

}

 

BinarySearchTree::NODE* BinarySearchTree::Search(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return NULL;

 

        NODE* node = m_root->Right;

       

        while (node != NULL)

        {

               if (node->Key == key)

                       return node;

 

               node = (node->Key > key) ? node->Left : node->Right;

        }

 

        return NULL;

}

 

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

 

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;      //자식 노드

        NODE* deleteNode;                      //삭제 노드

 

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

 

               //현재 노드를 부모 노드로

               parent = node;

 

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

 

        } while (node != NULL);

 

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

       

        //삭제할 노드 저장

        deleteNode = node;

 

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

 

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

                             

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

 

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

              

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

 

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

 

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

 

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

 

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

 

void BinarySearchTree::Print()

{

        if (IsEmpty())

        {

               printf("트리 비어 있음\n");

               return;

        }

 

        printf("전위순회");

 

        Preorder(m_root->Right);

 

        printf("\n");

}

 

bool BinarySearchTree::IsEmpty()

{

        if (m_root->Right == NULL)

               return true;

        else

               return false;

}

 

void BinarySearchTree::Clear()

{

        if (IsEmpty())

               return;

 

        Clear(m_root->Right);

 

        m_root->Right = NULL;

}

 

void BinarySearchTree::Preorder(NODE *node)

{

        if (node == NULL)

               return;

 

        //자신을 출력하고

        PrintNode(node);

 

        //왼쪽 방문

        Preorder(node->Left);

 

        //마지막으로 오른쪽 방문

        Preorder(node->Right);

}

 

//노드 데이터 프린트

void BinarySearchTree::PrintNode(NODE* node)

{

        printf(" -> K:%d", node->Key);

}

 

void BinarySearchTree::Clear(NODE *node)

{

        if (node == NULL)

               return;

 

        Clear(node->Left);

 

        Clear(node->Right);

 

        node->Left = NULL;

        node->Right = NULL;

 

        delete node;

        node = NULL;

}