이진 탐색 트리
이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료 구조이다. 이진 탐색 트리를 알기 위해선 먼저 이진 탐색을알아야 한다.
이진탐색
오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 임의의 접근을 허용해야되는 탐색의 특성상 연결리스트를 사용하기는 부적합하며 vector나 배열같은 것을 사용하는 것이 바람직하다. 시간 복잡도는 log(n)이다.
// 이진 탐색
vector<int>num;
void BinaryTree(int N)
{
int left = 0;
int right = num.size() - 1;
bool correct=false;
while (left<=right)
{
int mid = (right + left) / 2;
if (num[mid] == N)
{
cout << N << "=" << num[mid] << endl;
correct = true;
break;
}
if(num[mid]<N)
{
cout << N << ">" << num[mid] << endl;
left=mid+1;
}
if (num[mid] > N)
{
cout << N << "<" << num[mid] << endl;
right = mid-1;
}
}
if (correct == true)cout << "정답" << endl;
else cout << "오답" << endl;
}
이진 탐색 트리의 필요성
위와 같이 고정적인 배열형태의 이진탐색을 사용하면 매우 좋은 성능을 낼수 있다. 하지만 이러한 데이터 탐색의 문제는 데이터의 삽입/삭제될시 유동적인 처리가 곤란하다는 점이다. 이러한 문제점을 방지하고자 사용하는 것이 트리를 이용한 이진 탐색 트리이다.
이진 탐색 트리의 조건
이진 탐색 트리의 조건에는 아래와 같이 4개의 조건이 있다.
- 각 노드는 중복되지 않으며 유일하다.
- 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
- 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
- 좌우 서브 트리도 모두 이진 탐색 트리여야 한다
이진 탐색 트리 알고리즘
1.삽입
위와 같은 방식으로 처음 루트노드가 결정이 되면 그 수보다 작은수는 왼쪽으로 큰수는 오른쪽으로 가게된다.
2.삭제
삭제의 경우 삽입과는 다르게 3가지 경우의 수를 가지고 있다.
A.자식이 없는 경우
만약 삭제하고 싶은 노드가 자식을 가지고 있지 않다면 그냥 삭제가 가능하다.
B. 자식이 하나 일 경우
자식을 하나 가지고 있는 경우는 그 자식을 부모에게 넘겨주고 자신은 삭제하는 쪽으로 작동한다.
C. 자식이 두개 일 경우
자식을 두개 가지고 있는 경우 삭제하고 싶은 다음노드(크기가 큰 노드중에서 가장 작은 값)를 삭제하고 싶은 노드에 복사하고 복사한 노드를 삭제하는 알고리즘을 갖는다.
3. 순회 방법
A.전위순회
출력 우선순위가 중간>왼쪽>오른쪽인 순회방법
7->5->4->2->6->10->15->20->25->33
B.중위순회
출력 우선순위가 왼쪽>중간>오른쪽인 순회방법
2->4->5->6->7->10->15->20->25->33
C.후위순회
출력 우선순위가 왼쪽>오른쪽>중간인 순회방법
2->4->6->5->10->15->25->33->20->7
이진 탐색 트리 구현
//Binary_Tree.h
struct Node
{
Node* parent=nullptr;
Node* left=nullptr;
Node* right=nullptr;
int key = {};
};
class BinarySearch
{
public:
void Insert(int key);
void Print_Inorder(Node* node);
void Print_Inorder() { Print_Inorder(_root); }
void Print(Node* node, int x, int y);
void Print() { Print(_root,10,0); }
void Delete(int key);
void Delete(Node* node);
void Replace(Node* node1,Node* node2);
Node* Search_key(Node* node,int key);
Node* Max(Node* node);
Node* Min(Node* node);
Node* Next(Node* node);
private:
Node* _root=nullptr;
};//Binary_Tree.cpp
//_nil==nullptr
void BinarySearch::Insert(int key)
{
Node* newnode = new Node();
newnode->key = key;
if (_root == _nil)
{
_root = newnode;
return;
}
Node* node = _root;
Node* parent = _nil;
while (node!= _nil)
{
parent = node;
if (node->key < key)
{
node = node->right;
}
else if (node->key > key)
{
node = node->left;
}
}
newnode->parent = parent;
}
void BinarySearch::Delete(int key)
{
Node* deleteNode = Search_key(_root, key);
Delete(deleteNode);
}
void BinarySearch::Delete(Node* node)
{
if (node == _nil)return;
if (node->left == _nil)
{
Replace(node, node->right);
}
else if (node->right == _nil)
{
Replace(node, node->left);
}
else
{
Node* next=Next(node);
node->key = next->key;
Delete(next);
}
}
void BinarySearch::Replace(Node* node1, Node* node2)
{
if (node1->parent == _nil)_root = node2;
else if (node1 == node1->parent->left) node1->parent->left = node2;
else node1->parent->right = node2;
if (node2!= _nil)node2->parent = node1->parent;
delete node1;
}
Node* BinarySearch::Max(Node* node)
{
while (node->right!=_nil)
{
node=node->right;
}
return node;
}
Node* BinarySearch::Min(Node* node)
{
while (node->left!=_nil)
{
node= node->left;
}
return node;
}
Node* BinarySearch::Next(Node* node)
{
if (node->right!= _nil)return Min(node->right);
Node* parent = node->parent;
while (parent!= _nil && node==parent->right)
{
node = parent;
parent = parent->parent;
}
return parent;
}
댓글