반응형
이진탐색트리
*이진탐색트리의 가장 큰 용도는 map 자료구조 구현하는 것.
- 탐색이란?
레코드의 집합에서 특정한 레코드를 찾아내는 작업. 레코드는 하나 이상의 필드로 구성.
예) 학생정보 구조체 = 레코드 / 구조체의 멤버 변수인 학번,이름,주소,주민번호 = 필드
- 키(Key) : 레코드를 서로 구별하기 위해 필드 중에 서로 중복되지 않는 고유한 값을 갖는 필드.
예) 주민번호, 학번이 해당.
탐색은 주어진 키를 가진 레코드를 찾는 작업.
레코드가 노드에 저장되는 이진탐색트리에서는 주어진 키를 가진 노드를 찾아야 한다.
- 이진탐색트리(Binary Search Tree)의 정의
효율적인 탐색을 위한 이진트리 기반의 자료구조.
- 모든 노드는 유일한 키를 갖는다.
- 왼쪽 서브 트리 키들은 루트 키보다 작다.
- 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오른쪽 서브 트리도 이진탐색트리.
그림의 트리를 중위 순회 방법으로 순회하면 3,7,12,18,26,27,31 숫자의 오름차순으로 노드를 방문한다.
이진탐색트리는 이러한 성질을 가져서 어느 정도 정렬된 상태를 유지하고 있다.
- 이진탐색트리의 연산
일반 이진트리에서는 삽입이나 삭제를 위해 노드의 위치를 정하는 것이 쉽지 않았지만,
이진탐색트리에서는 이 연산들을 구현할 수 있다.
이진탐색트리의 조건을 유지하면서 삽입, 삭제, 탐색 연산을 구현.
- 탐색 연산
탐색이 가능하기 위해서는 트리가 주어진 키값에 대해 이진탐색트리 조건에 맞게 구성되어 있어야 한다.
* 키가 아닌 다른 필드를 이용한 탐색 가능?
가능은 하지만 일반적인 순회 알고리즘으로 모든 노드를 순서대로 검사해야 되기 때문에 효율이 떨어진다.
이진탐색트리에서 키값으로 key를 가진 노드를 탐색.
탐색은 항상 루트노드에서 시작.
루트노드와의 비교 결과는 다음 세 가지중 하나.
- key가 루트 키값과 같으면 루트== 찾는 노드. 탐색 성공.
- key가 루트 키값보다 작으면 찾는 노드는 왼쪽 서브트리에 있다. 탐색을 루트의 왼쪽 자식을 기준으로 다시 시작.
- key가 루트 키값보다 크면 찾는 노드는 오른쪽 서브트리에 있다. 탐색을 루트의 오른쪽 자식을 기준으로 다시 시작.
// 이진탐색트리의 순환적인 탐색함수
TNode* search(TNode* node,int key)
{
if (node == nullptr)
return nullptr;
else {
if (node->data == key) // key가 노드 n 키값과 같다면
return node; // 탐색 성공
else if (key < node->data) // key가 n 키값 보다 작다면
return search(node->left, key); // 왼쪽 서브트리 탐색
else // key가 n 키값 보다 크다면
return search(node->right, key); // 오른쪽 서브트리 탐색
}
}
// 이진탐색트리의 반복적인 탐색함수 -> 재귀보다 효율성 더 좋다.
TNode* search_iter(TNode* node,int key)
{
while (node != nullptr) {
if (key == node->data)
return node;
else if (key < node->data)
node = node->left;
else
node = node->right;
}
return nullptr; // 트리에 해당 키값 없음.
}
- 삽입 연산
- 먼저 탐색을 수행 : 같은 키 값을 갖는 노드가 없어야 하고, 탐색에 실패한 위치가 새로운 노드를 삽입하는 위치가 되기 때문.
- 탐색이 성공하면 키가 중복되므로 삽입 불가 / 탐색 실패하면 실패로 끝난 위치에 해당 노드를 삽입.
int insert(TNode* r, TNode* n)
{
// 1. 탐색
if (n->data == r->data)
return 0;
else if (n->data < r->data) { // 삽입할 노드의 키값이 루트 키값보다 작다면
if (r->left == nullptr) {
// 2. 삽입
r->left = n;
}
else
insert(r->left, n);
}
else { // 삽입할 노드의 키값이 루트 키값보다 크다면
if (r->right == nullptr) {
// 2. 삽입
r->right = n;
}
else
insert(r->right, n);
}
return 1;
}
- 삭제 연산
노드 삭제 후에도 이진탐색트리의 특성을 반드시 유지해야 되기 때문에 삭제 연산은 가장 복잡한 연산.
노드 삭제는 다음 3가지 경우를 고려.
- 단말 노드 삭제하는 경우
- 자식이 하나인 노드를 삭제하는 경우
- 자식이 두 개인 노드를 삭제하는 경우
어떤 노드를 삭제할 때는 부모 노드도 알아야 한다.
실제로 변경되는 것도 부모의 링크 필드.
노드를 트리에서 삭제한 후 동적 해제도 필요.
- 1. 단말 노드 삭제
부모 노드의 링크를 nullptr로 변경 후 삭제할 노드를 동적 해제.
- 2. 자식이 하나인 노드 삭제
자신을 삭제하고 삭제할 노드의 유일한 자식을 삭제할 노드의 부모 노드에 연결.
- 삭제할 노드의 자식이 왼쪽 / 오른쪽 자식일 수도 있다.
- 삭제할 노드가 부모의 왼쪽 / 오른쪽 자식일 수도 있다.
- 3. 두 개의 자식을 모두 갖는 노드 삭제
- 삭제할 노드를 대신할 적절한 후계자 노드를 찾는다.
후계자 노드는 삭제되는 노드와 가장 값이 비슷한 노드이다.
왼쪽 서브트리의 가장 큰 값(가장 오른쪽 노드) / 오른쪽 서브트리의 가장 작은 값(가장 왼쪽 노드)
-> 둘 중 어느 것을 선택해도 상관 X. 여기서는 오른쪽 서브 트리에서 제일 작은값으로 설정.
오른쪽 서브트리에서 왼쪽 자식 링크를 타고 NULL을 만날 때 까지 계속 진행하면 후계자 노드 탐색 가능.
노드를 삭제하는 과정
- 후계자 노드와 그의 부모노드를 찾는다.
- 후계자 노드를 삭제할 노드에 복사한다.
- 후계자 부모의 왼쪽 자식을 후계자 노드의 오른쪽 자식으로 변경. 후계자로 선택된 노드의 오른쪽 자식이 있을 수 있음을 유의.
- 이진탐색트리 구현 코드
#include <iostream>
using namespace std;
typedef int TElement;
typedef struct BinTrNode {
TElement data;
BinTrNode* left; // 왼쪽 자식 노드
BinTrNode* right; // 오른쪽 자식 노드
} TNode;
class CBinTree {
public:
void init_tree() { root = nullptr; }
bool is_empty() { return root == nullptr; }
TNode* get_root() { return root; }
void set_root(TNode* n) { root = n; }
TNode* create_tree(TElement val, TNode* l, TNode* r)
{
TNode* node = new TNode;
node->data = val;
node->left = l;
node->right = r;
return node;
}
void preorder(TNode* n) // 이진트리 전위 순회 함수
{
if (n != nullptr)
{
printf("[%d]", n->data); // 1. 루트 노드 처리
preorder(n->left); // 2. 왼쪽 서브트리 방문
preorder(n->right); // 3. 오른쪽 서브트리 방문
}
}
void inorder(TNode* n) // 이진트리 중위 순회 함수
{
if (n != nullptr)
{
inorder(n->left); // 1. 왼쪽 서브트리 방문
printf("[%d]", n->data); // 2. 루트 노드 처리
inorder(n->right); // 3. 오른쪽 서브트리 방문
}
}
void postorder(TNode* n) // 이진트리 후위 순회 함수
{
if (n != nullptr)
{
postorder(n->left); // 1. 왼쪽 서브트리 방문
postorder(n->right); // 2. 오른쪽 서브트리 방문
printf("[%d]", n->data); // 3. 루트 노드 처리
}
}
int count_node(TNode* n) // 이진트리 전체 노드 개수 구하는 순환 함수
{
if (n == nullptr)
return 0;
return 1 + count_node(n->left) + count_node(n->right); // 루트 + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수
}
int count_leaf(TNode* n) // 이진트리 단말 노드 개수 구하는 순환 함수
{
if (n == nullptr)
return 0;
if (n->left == nullptr && n->right == nullptr)
return 1;
else return count_leaf(n->left) + count_leaf(n->right); // 비단말 노드면 각각의 서브트리에 대해 순환호출 해 반환되는 두값을 더해 반환.
}
int calc_height(TNode* n)
{
if (n == nullptr)
return 0;
int hLeft = calc_height(n->left); // 왼쪽 서브트리 높이 계산해 저장
int hRight = calc_height(n->right); // 오른쪽 서브트리 높이 계산해 저장
return (hLeft > hRight) ? hLeft + 1 : hRight + 1; // 두 높이 중 더 높은 값에 1 더해서 반환
}
TNode* search(TNode* node,int key) // 이진탐색트리 탐색
{
if (node == nullptr)
return nullptr;
else {
if (node->data == key) // key가 노드 n 키값과 같다면
return node; // 탐색 성공
else if (key < node->data) // key가 n 키값 보다 작다면
return search(node->left, key); // 왼쪽 서브트리 탐색
else // key가 n 키값 보다 크다면
return search(node->right, key); // 오른쪽 서브트리 탐색
}
}
// key를 전달하면 전체 트리에서 해당 노드를 찾는 함수
void search_BST(int key) {
TNode* n = search(root, key);
if (n != nullptr) {
printf("탐색연산 성공 : [%d], 노드 주소 : 0x%x\n", n->data, n);
}
else
printf("탐색연산 실패 : [%d] 없음\n",key);
}
// 이진탐색트리의 반복적인 탐색함수 -> 재귀보다 효율성 더 좋다.
TNode* search_iter(TNode* node, int key)
{
while (node != nullptr) {
if (key == node->data)
return node;
else if (key < node->data)
node = node->left;
else
node = node->right;
}
return nullptr; // 트리에 해당 키값 없음.
}
int insert(TNode* r, TNode* n)
{
// 1. 탐색
if (n->data == r->data)
return 0;
else if (n->data < r->data) { // 삽입할 노드의 키값이 루트 키값보다 작다면
if (r->left == nullptr) {
// 2. 삽입
r->left = n;
}
else
insert(r->left, n);
}
else { // 삽입할 노드의 키값이 루트 키값보다 크다면
if (r->right == nullptr) {
// 2. 삽입
r->right = n;
}
else
insert(r->right, n);
}
return 1;
}
void insert_BST(int key) {
TNode* n = create_tree(key, nullptr, nullptr);
if (is_empty()) {
root = n;
}
else if (insert(root, n) == 0) // 삽입연산
delete n; // 삽입 실패라면 동적할당 해제
}
void delete_node(TNode* parent, TNode* node) { // 부모노드, 삭제할 노드
TNode *child, *succ, *succp;
// case 1 : 단말 노드 삭제
if (node->left == nullptr && node->right == nullptr) {
if (parent == nullptr) // 단말노드인데 부모가 NULL이면 root가 NULL인 것.
root = nullptr;
else {
if (parent->left == node) { // 부모의 왼쪽 자식이라면
parent->left = nullptr;
}
else // 부모의 오른쪽 자식이라면
parent->right = nullptr;
}
}
// case 2 : 자식이 하나인 노드 삭제
else if (node->left == nullptr || node->right == nullptr) {
child = (node->left != nullptr) ? node->left : node->right; // 삭제할 노드의 왼쪽 자식이 NULL이 아니라면 child 노드는 왼쪽, 아니면 오른쪽
if (node == root) { // 삭제할 노드가 루트라면
root = child; // 루트에 자식노드 대입
}
else if (parent->left == node) { // 삭제할 노드가 부모의 왼쪽 자식이라면
parent->left = child; // 부모의 왼쪽을 삭제할 노드의 자식으로 연결
}
else
parent->right = child;
}
// case 3 : 자식이 두개인 노드 삭제
else {
succp = node; // 후계자 노드의 부모 노드
succ = node->right; // 후계자 노드
while (succ->left != nullptr) { // 오른쪽 서브트리에서 왼쪽 자식 링크를 타고 NULL 만날 때 까지 진행
succp = succ;
succ = succ->left;
}
if (succp->left == succ) { // 후계 노드(succ)가 후계 부모(succp)의 왼쪽 자식이면
succp->left = succ->right; // succp의 왼쪽자식으로 succ의 오른쪽 자식 연결
}
else // 그렇지 않으면
succp->right = succ->right; // succ는 왼쪽 자식이 없음(왼쪽 자식 NULL 나올때 까지 진행한 것이기 때문)
node->data = succ->data; // 후계자 노드를 삭제할 노드에 복사한다.
node = succ; // 복사한 뒤 삭제할 노드를 succ 노드로 교체
}
delete node;
}
void delete_BST(int key) {
TNode* parent = nullptr;
TNode* node = root;
if (node == nullptr)
return;
while (node != nullptr && node->data != key) { // 삭제하려는 노드 탐색
parent = node;
node = (key < node->data) ? node->left : node->right; // key가 현재 노드의 키값보다 작으면 left노드로, 아니면 right 노드로
}
if (node == nullptr)
printf("삭제하려는 key가 트리안에 없습니다.\n");
else
delete_node(parent, node);
}
private:
TNode* root;
};
void main() {
CBinTree binTr;
// 삽입 연산 테스트
printf("[삽입 연산] : 35 18 7 26 12 3 68 22 30 99");
binTr.init_tree();
binTr.insert_BST(35);
binTr.insert_BST(18);
binTr.insert_BST(7);
binTr.insert_BST(26);
binTr.insert_BST(12);
binTr.insert_BST(3);
binTr.insert_BST(68);
binTr.insert_BST(22);
binTr.insert_BST(30);
binTr.insert_BST(99);
// 트리 정보 출력
printf("\n In-Order(중위순회) : "); binTr.inorder(binTr.get_root()); // 중위 순회는 정렬됨.
printf("\n Pre-Order(전위순회) : "); binTr.preorder(binTr.get_root());
printf("\n Post-Order(후위순회) : "); binTr.postorder(binTr.get_root());
printf("\n 노드의 개수 = %d\n ", binTr.count_node(binTr.get_root()));
printf("\n 단말노드의 개수 = %d\n ", binTr.count_leaf(binTr.get_root()));
printf("\n 트리의 높이 = %d\n ", binTr.calc_height(binTr.get_root()));
// 탐색 연산 테스트
binTr.search_BST(26);
binTr.search_BST(25);
// 삭제 연산 테스트
binTr.delete_BST(3);
printf("\ncase1. 단말 노드 삭제 <3> ->"); binTr.inorder(binTr.get_root());
binTr.delete_BST(68);
printf("\ncase2. 자식 한개인 노드 삭제 <68> ->"); binTr.inorder(binTr.get_root());
binTr.delete_BST(18);
printf("\ncase1. 자식 두개인 노드 삭제 <18> ->"); binTr.inorder(binTr.get_root());
binTr.delete_BST(35);
printf("\ncase1. 자식 두개인 노드 삭제 <35> ->"); binTr.inorder(binTr.get_root());
// 최종 트리 정보 출력
printf("\n 노드의 개수 = %d\n ", binTr.count_node(binTr.get_root()));
printf("\n 단말노드의 개수 = %d\n ", binTr.count_leaf(binTr.get_root()));
printf("\n 트리의 높이 = %d\n ", binTr.calc_height(binTr.get_root()));
}
- 이진탐색트리의 성능
이진탐색트리에서의 탐색, 삽입, 삭제 연산의 시간 복잡도는
트리의 높이를 h라고 했을 때 O(h).
n개의 노드를 갖는 이진탐색트리는 일반적인 이진트리의 높이가 log₂n이므로,
예) 이진탐색트리의 높이가 5일 때, 이 트리는 최대 몇개의 노드를 가질 수 있나? 2^5 - 1(루트노드) = 31개
이진탐색트리 연산의 평균적 경우 시간복잡도는 O(log₂n).
선형 탐색의 시간복잡도 O(n)과 비교하면 매우 탁월.
-> 좌우의 서브 트리가 균형을 이루고 있는 경우에만 해당. 한쪽으로 치우친 완전한 경사 이진트리는 트리의 높이가 n과 같게되어 탐색,삭제,삽입 시간이 선형탐색과 같은 O(n).
=>결국 이진탐색트리의 효율을 높이기 위해서 가능한 트리가 좌우로 균형잡히게 만들어아 햔다.
반응형
'코딩테스트 및 개인공부 > 자료구조' 카테고리의 다른 글
| [자료구조] [10] 우선순위 큐 (0) | 2022.01.08 |
|---|---|
| [자료구조] [8] 트리 (0) | 2021.12.29 |
| [자료구조] [7] 순환 (0) | 2021.12.29 |
| [자료구조] [6] 리스트 (0) | 2021.12.09 |
| [자료구조] [5] 포인터, 연결리스트 (0) | 2021.12.08 |
