이진검색트리 (BST)

이진 검색트리(BST)

일반 트리와 달리 BST의 재귀는 자료가

어떻게 접근되는가가 아니라 자료가 어떻게 정렬되는가에서 더 중요

 

 

BST의 정렬에서 핵심은 자료를 반으로 나눔으로써 검색 공간을 줄인다.

검색하고자 하는 자료들이 대기열에 들어가 있다고 하자. 대기열에서 첫번째 항목을 뽑아 그것을 트리의 루트로 한다.

대기열에서 다음 항목을 뽑아서 루트와 비교하고 그것보다 작으면 왼쪽자식으로 크면 오른쪽 자식으로 만든다.

나머지 항목들도 동일한 과정반복

현재 노드보다 작으면 왼쪽, 크면 오른쪽 따라가다가 자식이 없는 노드를 만나면 그 노드랑 비교 왼쪽 오른쪽 자식에 추가

 

자료검색또한 위의 과정과 동일하게 하면된다.

3을 찾는과정이라면 루트가 만약 4라면 3과 4를 비교해서 왼쪽으로 가고 등등...

 

BST검색 알고리즘은 대략 0(log2n)이 된다. 근데 이건 최선의 경우..최악은..다르다..

 

BST노드 제거 알고리즘이 있지만 여기서는 다루지 않음

게임 프로그래밍에서 BST가 필수적이라고 생각하지 않아서 그럼.

 

BST규칙

1. 왼쪽 하위 트리의 모든 노드는 현재 노드보다 작다

2. 오른쪽 하위 트리의 모든 노드는 현재 노드보다 크다

 

BST의 최악의 상황은 대기열에 12345가 들어간다고 하면됨.

1이 루트 2는 1의 오른쪽 자식 3은 2의 오른쪽 자식..............등등

그러면 쭉 연결된 목록처럼되버리며 검색도 0(n)이 된다.

그래서 자료가 삽입될 떄 트리가 좀 더 균등한 구조를 가지도록 일부 노드들을 회전시키는 방법이 사용되고

그것이 AVL, 적흑, 스플레이 트리 같은거다.

*삽입되는 데이터가 무작위적이면 그리 나쁘지 않은 트리가 되나, 정렬되어있는 상태라면 최적이 아닌 트리가 될 수 있다.

 

이진검색 트리의 내부는 이진 트리이다.

실제의 BST클래스는 하나의 컨테이너일뿐이다.

BST의 멤버변수는

이진트리, 루트 노드에 대한 포인터, 비교함수를 가리키는 함수 포인터를 가진다.

그런데 숫자에 대해서는 크다 작다가 명확한데 복잡한 구조체나 클래스의 인스턴스를 담는 경우에는 비교할 수 있는 수단이 필요함.

그래서 BST에 임의의 자료를 담을 수 있으려면 그러한 비교 수단이 BST 컨테이너 자체에(이진검색트리 안에) 고정되지 않아야 한다

그래서 함수 포인터를 가진다는것임(해쉬나 이진트리의 운행의 처리함수나 같은개념)

 

 

class BinarySearchTree
{
public:
 typedef BinaryTree<DataType> Node; //이진트리

//루트 노드에 대한 포인터

//반복자 처럼 사용하기 위해서 부모에서부터 내려간다는 개념을 두기위함
 Node* m_root; 

//int 형을 제외한 형(클래스)에 대해서 비교를 하기 위해서

int(*m_compare)(DataType, DataType); //비교함수를 가리키는 함수 포인터

 

template<class DataType>
class BinarySearchTree
{
public:
 typedef BinaryTree<DataType> Node; //이진트리
 Node* m_root;//루트 노드에 대한 포인터
 int(*m_compare)(DataType, DataType); //비교함수를 가리키는 함수 포인터

public:
 BinarySearchTree(int(*p_compare)(DataType, DataType))
 {
  m_root = nullptr;
  m_compare = p_compare;
 }

 //루트노드를 삭제하면 자동적으로 트리 전체가 삭제된다. 왜냐?
 //BinaryTree의 소멸자가 재귀적으로 작동함(이미 BinaryTree에서 구현했잖야..Destroy)
 ~BinarySearchTree()
 {
  if (m_root != 0)
  {
   delete m_root;
  }
 }

//자료의 중복 삽입을 보통허용하지 않은데 밑에 insert는 허용함

 void Insert(DataType p_data)
 {
  Node* current = m_root; //반복자 역활
  if (m_root == nullptr)
  {
   m_root = new Node(p_data);
  }
  else
  {
   whle(current != nullptr)
   {
    if (m_compare(p_data, current->p_data) < 0) //현재 노드의 자료를 삽입할 자료와 비교
    {
     //0보다 작으면 왼쪽 자식에 삽입

     //왼쪽 자식이 존재하지 않으면 주어진 자료를 실제로 삽입
     if (current->m_left == nullptr)
     {
      current->m_left = new Node(p_data);
      current->m_left->m_parent = current;
      current = nullptr;
     }
     //존재한다면 현재 반복자를 그 왼쪽 자식 노드로 옮긴다.
     else
     {
      current = current->m_left;
     }
    }

    //0보다 크므로 오른쪽 자식에 삽입
    else
    {
     if (current->m_right == nullptr)
     {
      current->m_right = new Node(p_data);
      current->m_right->m_parent = current;
      current = nullptr;
     }
     else
     {
      current = current->m_right;
     }
    }
   }
  }
 }

 Node* Find(DataType p_data)
 {
  Node* current = m_root;
  int temp;
  while (current != 0)
  {
   temp = m_compare(p_data, current->m_data);
   if (temp == 0)
   {
    return current;
   }
   if (temp < 0)
   {
    current = current->m_left;
   }
   else
   {
    current = current->m_right;
   }
  }
  return 0;
 }
};

//비교함수
int CompareInts(int left, int right)
{
 return left - right;
}

#endif 

 

이진검색 트리가 해시 테이블보다 더 나은 점은 별로 없다.

해시테이블검색시간은 O(c)에 가깝지만 BST는 최적이라고해도 O(c)보다 느린 O(log2n)이다

재귀적으로 저장한다는 점만 알면 된다. 이진 공간 분할 트리?에서 중요함..(BSP 한번 공부해야할듯..)

실제 존 카멕의 둠에서 2차원 BSP를 사용함

BSP 개념은 BST와 매우 비슷..