알고리즘/C++

8. 이진 탐색 트리 (Binary Search Tree, BST)

dyeoma 2020. 7. 25. 17:23

dyeoma.tistory.com/20

 

이진 탐색 트리 (Binary Search Tree)

정의 모든 원소는 키를 가지며 동일한 키가 없음 왼쪽 sub tree에 있는 key 값 < root의 key 값 root의 key 값 < 오른쪽 sub tree에 있는 key 값 왼쪽 sub tree와 오른쪽 sub tree 모두 이진탐색트리 장점 임의의..

dyeoma.tistory.com

 

탐색 함수 - O(h) 소요  [h = 트리 높이]

template <class Type>
BstNode <Type> *BST<Type>::IterSearch (const Element<Type> &x)
   for (BstNode<Type *t=root; t; ){
      if(x.key < t->data.key)
         t = t->LeftChild;
      else if(x.key > t->data.key)
         t = t->rightChild;
      else
         return t;
   }
   return 0;	// 찾는 값이 없을 때 null 반환
}

 

 

삽입 함수 - O(h) 소요  [h = 트리 높이]

template <class Type>
Boolean BST<Type>::Insert (const Element <Type> &x) {
   BstNode<Type> *p = root;	
   BstNode<Type> *q = 0;	// q는 p의 parent
   
   while (p) {
      q = p;
      if (x.key < p->data.key)
         p = p->LeftChild;
      else if (x.key > p->data.key)
         p = p->RightChild;
         
      else		// x.key 값 이미 존재
         return FALSE;	// 삽입 실패
   }
   
   // 삽입 수행
   p = new BstNode<Type>;
   p->Leftchild = p->RightChild = 0;
   p->data = x;
   
   if (!root)		// empty tree
      root = p;
   
   if (x.key < q->data.key)
      q->LeftChild = p;
   else if (x.key > q->data.key)
      q->RightChild = p;
   
	return TRUE;	// 삽입 성공
}