📒 이진 탐색 트리(Binary Search Tree)
📌 이진 탐색 트리(Binary Search Tree)란?
- 이진 탐색 트리는 이진 트리 기반의 탐색을 위한 자료구조이다.
- 효율적인 탐색을 위해 고안된 자료구조이다.
📌 이진 탐색 트리 규칙
- 모든 노드의 key는 중복되지 않는다.
- 노드는 왼쪽 자식 노드보다 항상 크다.
- 노드는 오른쪽 자식 노드보다 항상 작다.
📌 탐색 트리 특성 비교
일반 이진 탐색 특성
- 중앙값을 알아야 하므로
배열에서만 사용할 수 있다. - 연결 리스트는 이진 탐색하기에 적합하지 않다.
- 배열의 크기가 정적이어야 한다.
이진 탐색 트리 특성
- 배열을 사용하여 탐색할 때 보다 시간 복잡도가 줄어든다. O(log N)
- 데이터 집합의 크기와 순서가 동적으로 바뀌어도 문제가 없다.
- 트리의 모양이 한쪽으로 치우치게 되면 트리 탐색의 장점인 O(log N) 시간 복잡도가 마치 배열을 탐색하듯이 O(N)에 가까워지게 된다.
- 따라서 이진 탐색 트리에 데이터를 추가 및 삭제할 때 트리 모양이 한족으로 치우치지 않고 균형된 모양을 유지하면 시간 복잡도가 늦춰지는 것을 방지할 수 있다.
(ex. Red- Black Tree https://velog.io/@liz/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-red-black-tree)
📌 이진 탐색 트리의 탐색 과정
- 루트 노드부터 시작하여 찾을 값과 크기를 비교하며 결과에 따라 방향을 결정하여 내려온다.
- 찾으려는 값 < 현재 노드의 값 : 왼쪽 자식 노드로
- 찾으려는 값 > 현재 노드의 값 : 오른쪽 자식 노드로
- 일치하는 값을 찾을 때까지 1, 2 과정을 반복한다.
📌 이진 탐색 트리의 탐색 삽입
- 이진 탐색 트리의 규칙을 유지해야 하므로 새 노드가 삽입될 때 또한 이진 탐색으로 적합한 위치를 찾아야 한다.
- 탐색 과정과 마찬가지의 과정으로 위치를 찾는다.
- 더 이상 내려갈 곳이 없으면 리프 노드의 자식으로 추가된다.
📌 이진 탐색 트리의 탐색 삭제
삭제할 노드의 자식이 0개일 때
- 자식이 0개인 경우에는 아무런 문제 없이 삭제할 수 있다.
삭제할 노드의 자식이 1개일 때
- 자식이 1개인 경우에는 자식을 삭제한 노드의 부모와 연결해 주어야 한다.
삭제할 노드의 자식이 2개일 때
- 자식이 2개인 경우에는 자식을 삭제한 노드의 부모 노드와 연결하게 되면 이진 탐색 트리의 규칙이 무너지게 된다.
- 때문에, 삭제한 노드와 가장 근사한 값을 찾아 연결해 주어야 한다.
- 그렇다면, 삭제한 노드의 왼쪽 서브 트리에서 가장 큰 값과, 오른쪽 서브 트리에서 가장 작은 값 중, 어떤 것을 선택하여도 문제가 없다.
📌 이진 탐색 트리의 탐색 순회
📝 이진 탐색 트리 구현(C++)
// BinarySearchTree.h
#pragma once
struct Node {
int Data = 0;
Node* Parent = nullptr;
Node* LeftChild = nullptr;
Node* RightChild = nullptr;
};
class BinarySearchTree
{
private:
Node* mRoot;
public:
BinarySearchTree() {
mRoot = nullptr;
}
void Insert(int data); // 삽입
Node* Search(Node* node, int data); // 탐색
void Replace(Node* u, Node* v); // 트리 교체
void Delete(int data); // 삭제
void Delete(Node* node); // 삭제
Node* Min(Node* node); // 최솟값
Node* Max(Node* node); // 최댓값
Node* Next(Node* node); // 다음 값
void Print(Node* node); // 트리 출력(중위 순회)
Node* GetRoot(); // 루트 노드 반환
};
// BinarySearchTree.cpp
#include <iostream>
#include "BinarySearchTree.h"
using namespace std;
/// <summary>
/// 데이터 삽입 함수
/// </summary>
/// <param name="삽입할 데이터"></param>
void BinarySearchTree::Insert(int data)
{
Node* newNode = new Node;
newNode->Data = data;
if (!mRoot) // root가 없으면
{
mRoot = newNode;
return;
}
Node* node = mRoot;
Node* parent = nullptr;
while (node)
{
parent = node;
if (parent->Data > data)
node = parent->LeftChild;
else
node = parent->RightChild;
}
newNode->Parent = parent;
if (data < parent->Data)
parent->LeftChild = newNode;
else
parent->RightChild = newNode;
}
/// <summary>
/// 이진 트리 탐색 함수
/// </summary>
/// <param name="루트 노드"></param>
/// <param name="탐색할 데이터"></param>
/// <returns>탐색할 데이터의 노드</returns>
Node* BinarySearchTree::Search(Node* node, int data)
{
// 못 찾으면 nullptr
if (!node || node->Data == data)
return node;
// node의 data보다 작으면 왼쪽
if (node->Data > data)
return Search(node->LeftChild, data);
// 그 외는 오른쪽
else
return Search(node->RightChild, data);
}
/// <summary>
/// 서브 트리 교체 함수
/// </summary>
/// <param name="삭제한 노드"></param>
/// <param name="이어 붙일 노드"></param>
void BinarySearchTree::Replace(Node* deleteNode, Node* attachNode)
{
if (!deleteNode->Parent) // deleteNode가 루트 노드라면
mRoot = attachNode;
else if (deleteNode->Parent->LeftChild == deleteNode) // deleteNode가 왼쪽 노드라면
deleteNode->Parent->LeftChild = attachNode;
else // deleteNode가 오른쪽 노드라면
deleteNode->Parent->RightChild = attachNode;
// nullptr 예외 처리
if (attachNode)
attachNode->Parent = deleteNode->Parent;
delete deleteNode;
}
/// <summary>
/// 원하는 데이터의 노드 삭제
/// </summary>
/// <param name="삭제할 데이터"></param>
void BinarySearchTree::Delete(int data)
{
Node* deleteNode = Search(mRoot, data);
Delete(deleteNode);
}
/// <summary>
/// 노드 삭제 함수
/// </summary>
/// <param name="삭제할 노드"></param>
void BinarySearchTree::Delete(Node* node)
{
if (!node)
return;
// 자식 여부에 따라 분기
if (!node->LeftChild) // 왼쪽 자식이 없을 때
Replace(node, node->RightChild);
else if (!node->RightChild) // 오른쪽 자식이 없을 때
Replace(node, node->LeftChild);
else
{
Node* next = Next(node);
node->Data = next->Data;
Delete(next);
}
}
/// <summary>
/// 트리의 최솟값을 찾는 함수
/// </summary>
/// <param name="루트 노드"></param>
/// <returns>트리의 최솟값</returns>
Node* BinarySearchTree::Min(Node* node)
{
if (!node) // 노드가 없으면 nullptr
return nullptr;
while (node->LeftChild) // 가장 작은 값 찾기
node = node->LeftChild;
return node;
}
/// <summary>
/// 트리의 최댓값을 찾는 함수
/// </summary>
/// <param name="node">루트 노드</param>
/// <returns>트리의 최댓값</returns>
Node* BinarySearchTree::Max(Node* node)
{
if (!node) // 노드가 없으면 nullptr
return nullptr;
while (node->RightChild) // 가장 큰 값 찾기
node = node->RightChild;
return node;
}
/// <summary>
/// 해당 노드 기준으로 바로 다음 값(큰 값)을 찾는 함수
/// </summary>
/// <param name="다음 값을 찾을 노드"></param>
/// <returns>해당 노드의 다음으로 큰 노드 반환</returns>
Node* BinarySearchTree::Next(Node* node)
{
// 오른쪽 자식 노드 있으면 오른쪽 자식 노드 트리에서 최솟값 반환(next 값)
if (node->RightChild)
return Min(node->RightChild);
Node* parent = node->Parent;
// 부모 노드가 존재하고, 현재 노드가 부모 노드의 오른쪽 자식일 때
// 오른쪽 자식이 아닌 부모 노드까지 올라간 후, 그 노드의 부모 노드(next 값) 반환
while (parent && node == parent->RightChild)
{
node = parent;
parent = node->Parent;
}
// 현재 노드가 왼쪽 자식이면 어떠한 분기도 거치지 않고 바로 부모 노드(next 값) 반환
return parent;
}
/// <summary>
/// 트리 출력 함수
/// </summary>
/// <param name="루트 노드"></param>
void BinarySearchTree::Print(Node* node)
{
// 중위 순회
if (!node)
return;
Print(node->LeftChild);
cout << node->Data << " ";
Print(node->RightChild);
}
/// <summary>
/// 루트 노드 반환 함수
/// </summary>
/// <returns>루트 노드</returns>
Node* BinarySearchTree::GetRoot()
{
return mRoot;
}
#include "BinarySearchTree.h"
int main() {
BinarySearchTree bst;
bst.Insert(25);
bst.Insert(40);
bst.Insert(10);
bst.Delete(40);
bst.Insert(50);
bst.Insert(35);
bst.Insert(30);
bst.Delete(10);
bst.Print(bst.GetRoot());
return 0;
}
Output:
25 30 35 50
복습하기 위해 쓰는 글