※ 이진 탐색 트리 (Binary Search Tree)
이진 탐색 트리는 효율적인 탐색작업(search)을 위한 자료구조로 다음과 같은 특징을 갖는다.
모든 node는 유일한 key를 갖는다.
왼쪽 sub tree의 key값 < root의 key 값 < 오른쪽 sub tree의 key값
모든 sub tree는 BST를 만족한다.
즉, 삽입 삭제가 다음 그림과 같이 진행된다.
선형 자료구조와 달리 이전 시간의 트리에서 삽입과 삭제, 탐색을 위해 node의 위치를 지정하는 것이 쉽지 않다.
하지만 BST에서는 이 연산들을 구체화 할 수 있고 또한 key값을 기준으로 정렬이 가능하다.
※ BST 기본 틀 설계
☠︎ skeleton code
- BinaryNode.h
#include <iostream>
class BinaryNode{
protected:
int data;
BinaryNode* left;
BinaryNode* right;
public:
BinaryNode(int val = 0, BinaryNode *l = nullptr, BinaryNode *r = nullptr) : data(val), left(l), right(r) { }
void setData(int val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
int getData() const { return data; }
BinaryNode* getLeft() const { return left; }
BinaryNode* getRight() const { return right; }
bool isLeaf() const { return left == nullptr && right == nullptr; }
};
- BinaryTree.h
#include "BinaryNode.h"
using namespace std;
class BinaryTree {
private:
BinaryNode *root;
public:
BinaryTree() : root(nullptr) { };
void setRoot(BinaryNode * node) { root = node; }
BinaryNode * getRoot() { return root; }
bool isEmpty() { return root == nullptr; }
// 이진트리의 순회연산 (전위, 중위, 후위, 레벨 순회)
void inorder() { cout << endl << "inorder: "; inorder(root); }
void inorder(BinaryNode *node) {
if (node != nullptr) {
inorder(node->getLeft());
cout << node->getData() << " ";
inorder(node->getRight());
}
}
void preorder() { cout << endl << "preorder: "; preorder(root); }
void preorder(BinaryNode *node) {
if (node!= nullptr) {
cout << node->getData() << " ";
preorder(node->getLeft());
preorder(node->getRight());
}
}
void postorder() { cout << endl << "postorder: "; postorder(root); }
void postorder(BinaryNode *node) {
if (node!= nullptr) {
postorder(node->getLeft());
postorder(node->getRight());
cout << node->getData() << " ";
}
}
// 이진트리의 추가 연산 (이진트리 노드의 개수 구하기 ,단말노드개수 구하기, 높이 구하기)
int getCount() { return isEmpty() ? 0 : getCount(root); }
int getCount(BinaryNode *node) {
if (node == nullptr) return 0;
return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}
int getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); }
int getLeafCount(BinaryNode *node) {
if (node == nullptr) return 0;
if (node->getLeft()) return 1;
else
return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}
int getHeight() { return isEmpty() ? 0 : getHeight(root); }
int getHeight(BinaryNode *node) {
if (node == nullptr) return 0;
int hLeft = getHeight(node->getLeft());
int hRight = getHeight(node->getRight());
return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}
};
- BST.h
#include "BinaryTree.h"
class BST : public BinaryTree {
public:
BST(){}
~BST(){}
BinaryNode *search(int key) {}
BinaryNode *search(BinaryNode *n, int key){}
void insert(BinaryNode *n){}
void insert(BinaryNode *r, BinaryNode *n){}
void remove(int data){}
void remove(BinaryNode *parent, BinaryNode *node){}
};
※ BST의 탐색연산 (search)
✯ BST의 search Algorithm
search (root, key)
if root == null
then return null;
if key = KEY(root)
then return root;
else if key < KEY(root)
then return search(LEFT(root), key);
else return search(RIGHT(root), key);key값으로 node를 탐색하는 함수로 2가지 방식으로 구현이 가능하다.
- 순환적인 방법
BinaryNode *search(BinaryNode *n, int key){
if (n == NULL) return NULL;
if (key == n->getData()) return n; // key == 현재 node의 data
else if (key < n->getData()) return search(n->getLeft(), key); // key < 현재 node의 data
else return search(n->getRight(), key); // key > 현재 node의 data
}- 반복적인 방법 (효율성의 측면에서 훨씬 우수)
BinaryNode *search(BinaryNode *n, int key){
while(n != nullptr){
if(key == n->getData())
return n;
else if(key < n->getData())
n = n->getLeft();
else
n = n->getRight();
}
return nullptr;
}
※ BST의 삽입연산 (insert)
BST에서 삽입을 위해 탐색이 선행되어야 한다!
( ∵ BST에서는 같은 key값을 갖는 node가 없어야 하기 때문! )
( ∵ BST에서는 탐색에 실패한 위치 = NULL값 = new node를 insert하는 위치 )
✯ BST의 insert Algorithm
insert (root, n)
if KEY(n) == KEY(root)
then return;
else if KEY(n) < KEY(root) then
if LEFT(root) == null
then LEFT(root) <- n;
else insert(LEFT(root), n);
else
if RIGHT(root) == null
key값으로 node를 탐색하는 함수로 2가지 방식으로 구현이 가능하다.
- 순환적인 방법
void insert(BinaryNode *r, BinaryNode *n){
if (n->getData() == r->getData())
return;
else if (n->getData() < r->getData()){
if (r->getLeft() == nullptr)
r->setLeft(n);
else
insert(r->getLeft(), n); // recursive insertion
}
else {
if (r->getRight() == nullptr)
r->setRight(n);
else
insert(r->getRight(), n); // recursive insertion
}
}key값으로 node를 탐색하는 함수로 2가지 방식으로 구현이 가능하다.
- 반복적인 방법 (위와 동일한 방법으로 변환 가능)
※ BST의 삭제연산 (delete)
앞의 두 연산보다 더욱 중요한 연산으로 BST에서 가장 복잡한 연산이다. 다음 3가지의 경우를 고려해야 하기 때문이다.
case1. 삭제하려는 node가 leaf node인 경우. --> 그냥 삭제하면 되서 가장 간단!
case2. 삭제하려는 node가 왼쪽이나 오른쪽 sub tree중 하나만 갖는 경우 --> 해당 sub tree를 부모로!
case3. 삭제하려는 node가 양쪽 sub tree 모두 갖는 경우 --> 가장 복잡!
➣ case 1. 삭제 node가 leaf node
i) 부모 노드를 찾아서
ii) 부모 노드의 link 영역을 nullptr로 만든다.
iii) leaf node를 최종적으로 동적으로 해제한다.
즉, 부모 노드를 반.드.시! 알아야 한다!
➣ case 2. 삭제 node가 sub tree 하나만 갖고 있음
i) 해당 노드는 삭제하고
ii) 유일한 자식을 부모 노드에 붙여준다.
즉, 부모와 자식노드를 둘 다! 알아야 한다!
➣ case 3. 삭제 node가 sub tree 모두 갖고 있음
가장 핵심은 "삭제되는 노드와 가장 값이 비슷한 노드"가 핵심!
i) left sub tree의 최하단우측 node와 right sub tree의 최하단좌측 node 중 선택 (위 그림에서 30과 50중 선택)
(오른쪽 서브트리의 제일 작은 값을 선택했다 가정)
이때, 여러 부모 및 자식 노드의 정보가 필요해서 매우 구현이 복잡해진다.
※ BST 구현
- BinaryNode.h
#include <iostream>
class BinaryNode{
protected:
int data;
BinaryNode* left;
BinaryNode* right;
public:
BinaryNode(int val = 0, BinaryNode *l = nullptr, BinaryNode *r = nullptr) : data(val), left(l), right(r) { }
void setData(int val) { data = val; }
void setLeft(BinaryNode* l) { left = l; }
void setRight(BinaryNode* r) { right = r; }
int getData() const { return data; }
BinaryNode* getLeft() const { return left; }
BinaryNode* getRight() const { return right; }
bool isLeaf() const { return left == nullptr && right == nullptr; }
};- BinaryTree.h
#include "BinaryNode.h"
using namespace std;
class BinaryTree {
public:
BinaryNode *root;
BinaryTree() : root(nullptr) { };
void setRoot(BinaryNode * node) { root = node; }
BinaryNode * getRoot() { return root; }
bool isEmpty() { return root == nullptr; }
// 이진트리의 순회연산 (전위, 중위, 후위, 레벨 순회)
void inorder() { cout << endl << "inorder: "; inorder(root); }
void inorder(BinaryNode *node) {
if (node != nullptr) {
inorder(node->getLeft());
cout << node->getData() << " ";
inorder(node->getRight());
}
}
void preorder() { cout << endl << "preorder: "; preorder(root); }
void preorder(BinaryNode *node) {
if (node!= nullptr) {
cout << node->getData() << " ";
preorder(node->getLeft());
preorder(node->getRight());
}
}
void postorder() { cout << endl << "postorder: "; postorder(root); }
void postorder(BinaryNode *node) {
if (node!= nullptr) {
postorder(node->getLeft());
postorder(node->getRight());
cout << node->getData() << " ";
}
}
// 이진트리의 추가 연산 (이진트리 노드의 개수 구하기 ,단말노드개수 구하기, 높이 구하기)
int getCount() { return isEmpty() ? 0 : getCount(root); }
int getCount(BinaryNode *node) {
if (node == nullptr) return 0;
return 1 + getCount(node->getLeft()) + getCount(node->getRight());
}
int getLeafCount() { return isEmpty() ? 0 : getLeafCount(root); }
int getLeafCount(BinaryNode *node) {
if (node == nullptr) return 0;
if (node->getLeft()) return 1;
else
return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
}
int getHeight() { return isEmpty() ? 0 : getHeight(root); }
int getHeight(BinaryNode *node) {
if (node == nullptr) return 0;
int hLeft = getHeight(node->getLeft());
int hRight = getHeight(node->getRight());
return (hLeft > hRight) ? hLeft + 1 : hRight + 1;
}
};- BST.h
#include "BinaryTree.h"
class BST : public BinaryTree {
public:
BST(){}
~BST(){}
BinaryNode *search(int key) {
BinaryNode *node = search(root, key);
if (node != NULL) {
cout << "탐색 성공: key값이 " << node->getData() << "인 노드 = " << node << endl;
}
else
cout << "탐색 실패: key값이 " << key << "인 노드 없음" << endl;
return node;
}
BinaryNode *search(BinaryNode *n, int key){
while(n != nullptr){
if(key == n->getData())
return n;
else if(key < n->getData())
n = n->getLeft();
else
n = n->getRight();
}
return nullptr;
}
void insert(BinaryNode *n){
if ( n == nullptr ) return;
if (isEmpty()) root = n;
else insert(root, n);
}
void insert(BinaryNode *r, BinaryNode *n){
if (n->getData() == r->getData())
return;
else if (n->getData() < r->getData()){
if (r->getLeft() == nullptr)
r->setLeft(n);
else
insert(r->getLeft(), n); // recursive insertion
}
else {
if (r->getRight() == nullptr)
r->setRight(n);
else
insert(r->getRight(), n); // recursive insertion
}
}
void remove(int key){
if (isEmpty()) return;
BinaryNode *parent = nullptr;
BinaryNode *node = root;
while(node != nullptr && node->getData() != key){
parent = node;
node = (key < node->getData()) ? node->getLeft() : node->getRight();
}
if (node == nullptr){
cout << "Error: key is not in the tree!" << endl;
return;
}
else
remove(parent, node);
}
void remove(BinaryNode *parent, BinaryNode *node){
// case 1: leaf node 삭제
if (node->isLeaf()) {
if (parent == nullptr)
root = nullptr;
else {
if (parent->getLeft() == node)
parent->setLeft(nullptr);
else
parent->setRight(nullptr);
}
}
// case 2: 1개 자식만 갖는 node 삭제
else if (node->getLeft() == nullptr || node->getRight() == nullptr) {
BinaryNode *child = (node->getLeft() != nullptr) ? node->getLeft() : node->getRight();
if (node == root)
root = child;
else {
if (parent->getLeft() == node)
parent->setLeft(child);
else
parent->setRight(child);
}
}
// case 3: 2개 자식 모두를 갖는 node를 삭제
else {
BinaryNode *newnode = node;
BinaryNode *newnode_parent = node->getRight();
while (newnode->getLeft() != nullptr) {
newnode_parent = newnode;
newnode = newnode->getLeft();
}
if (newnode_parent->getLeft() == newnode)
newnode_parent->setLeft(newnode->getRight());
else
newnode_parent->setRight(newnode->getRight());
node->setData(newnode->getData());
node = newnode;
}
delete node; // 메모리 동적 해제
}
};- main.cpp
#include "BST.h"
#include <iostream>
using namespace std;
int main() {
BST tree;
tree.insert(new BinaryNode(35));
tree.insert(new BinaryNode(18));
tree.insert(new BinaryNode(7 ));
tree.insert(new BinaryNode(26));
tree.insert(new BinaryNode(12));
tree.insert(new BinaryNode(3 ));
tree.insert(new BinaryNode(68));
tree.insert(new BinaryNode(22));
tree.insert(new BinaryNode(30));
tree.insert(new BinaryNode(99));
cout << "노드 개수: " << tree.getCount() << endl;
cout << "leaf 개수: " << tree.getLeafCount() << endl;
cout << "height: " << tree.getHeight() << endl;
tree.preorder();
tree.inorder();
tree.postorder();
cout << endl;
tree.search(26);
tree.search(25);
cout << endl;
cout << "case 1 ==> 노드 3 삭제" << endl;
tree.remove(3);
cout << "case 2 ==> 노드 68 삭제" << endl;
tree.remove(68);
cout << "case 3 ==> 노드 18 삭제" << endl;
tree.remove(18);
tree.preorder();
cout << endl;
cout << "case 3 ==> root 삭제" << endl;
tree.remove(35);
tree.preorder();
cout << endl;
cout << "노드 개수: " << tree.getCount() << endl;
cout << "leaf 개수: " << tree.getLeafCount() << endl;
cout << "height: " << tree.getHeight() << endl;
/********************************************************************/
// 노드 개수: 10
// leaf 개수: 1
// height: 4
//
// preorder: 35 18 7 3 12 26 22 30 68 99
// inorder: 3 7 12 18 22 26 30 35 68 99
// postorder: 3 12 7 22 30 26 18 99 68 35
// 탐색 성공: key값이 26인 노드 = 0x6000030c9200
// 탐색 실패: key값이 25인 노드 없음
//
// case 1 ==> 노드 3 삭제
// case 2 ==> 노드 68 삭제
// case 3 ==> 노드 18 삭제
//
// preorder: 35 7 12 26 22 30 99
// case 3 ==> root 삭제
//
// preorder: 12 7 26 22 30 99
// 노드 개수: 6
// leaf 개수: 1
// height: 4
}
※ BST의 성능분석
트리의 높이를 h라 할 때, 일반적인 선형자료구조의 경우 O(h)가 된다.
이진트리의 경우, 보통 트리의 높이가 log h가 되므로 평균적인 시간복잡도는 O(log n)으로 매우 탁월함을 보여준다.
다만 이런 이진탐색트리의 경우 트리가 간혹 좌우로 불균형해져 트리의 높이가 log n이 만들어 지지 않는 경우가 발생할 수 있다.
이를 보완하는 방법으로 트리의 높이를 항상 log n으로 한정시키는 AVL 트리가 있다.
Adelson Velskii Landis tree는 이진탐색트리의 노드의 불균형 문제를 해결한 트리로 밑에서 설명하겠다.
※ AVL 트리 (Adelson Velskii Landis Tree)
AVL 트리는 왼쪽과 오른쪽 sub tree간의 높이차가 1 이하인 BST이다. 이를 통해 O(log n)의 시간을 항상 보장한다!
탐색연산은 BST와 동일하지만 삽입, 삭제의 경우가 균형이 깨지기에 AVL 트리는 삽입과 삭제에 추가적 연산을 진행한다.
이런 균형이 깨진 트리를 다시 균형있게 만드는 방법으로 다음 4가지 방법이 있다.
새로 삽입된 노드 N과 N에서 가장 가까운 조상 노드 A에 대해
‣ LL 타입: N이 A의 왼쪽 sub tree의 왼쪽 sub tree로 삽입
‣ LR 타입: N이 A의 왼쪽 sub tree의 오른쪽 sub tree로 삽입
‣ RR 타입: N이 A의 오른쪽 sub tree의 오른쪽 sub tree로 삽입
‣ RL 타입: N이 A의 오른쪽 sub tree의 왼쪽 sub tree로 삽입
‣ LL 회전: 오른쪽으로 회전
‣ LR 회전: 왼쪽-오른쪽으로 회전
‣ RR회전: 왼쪽으로 회전
‣ RL 회전: 오른쪽-왼쪽으로 회전
✯ AVL Tree의 Rotate Algorithm
☞ 단순 회전 알고리즘(LL, RR)
rotate_LL(A)
B <- A의 왼쪽 자식
B의 오른쪽 자식을 A의 왼쪽 자식으로 만든다.
A를 B의 오른쪽 자식 노드로 만든다.
rotate_RR(A)
B <- A의 오른쪽 자식
B의 왼쪽 자식을 A의 오른쪽 자식으로 만든다.
A를 B의 왼쪽 자식 노드로 만든다.
☞ 이중 회전 알고리즘 (RL, LR)
rotate_RL(A)
B <- A의 오른쪽 자식
rotate_LL(B)가 반환하는 노드를 A의 오른쪽 자식으로 만든다.
rotate_LR(A)
B <- A의 왼쪽 자식
rotate_RR(B)가 반환하는 노드를 A의 왼쪽 자식으로 만든다.
rotate_LL(A)
※ AVL Tree 구현
- AVLTree.h
#include "BST.h"
class AVLTree : public BST {
public:
int getHeightDiff(BinaryNode *node) {
if (node == nullptr) return 0;
int hLeft = getHeight(node->getLeft());
int hRight = getHeight(node->getRight());
return hRight - hLeft;
}
// LL rotation
BinaryNode *LL (BinaryNode *parent){
BinaryNode *child = parent->getLeft();
parent->setLeft(child->getRight());
child->setRight(parent);
return child;
}
// RR rotation
BinaryNode *RR (BinaryNode *parent){
BinaryNode *child = parent->getRight();
parent->setRight(child->getLeft());
child->setLeft(parent);
return child;
}
// LR rotation
BinaryNode *LR (BinaryNode *parent){
BinaryNode *child = parent->getLeft();
parent->setLeft(RR(child));
return LL(parent);
}
// RL rotation
BinaryNode *RL (BinaryNode *parent){
BinaryNode *child = parent->getRight();
parent->setRight(LL(child));
return RR(parent);
}
// AVL Tree
BinaryNode *reBalance (BinaryNode *parent) {
int hDiff = getHeightDiff(parent);
if (hDiff > 1) {
if (getHeightDiff(parent->getLeft()) > 0)
parent = LL(parent);
else
parent = RR(parent);
}
else if (hDiff < -1) {
if (getHeightDiff(parent->getRight()) < 0)
parent = RR(parent);
else
parent = RL(parent);
}
return parent;
}
// AVL Tree insertion
void insert (int data) {
if (isEmpty())
root = new BinaryNode(data);
else
root = insertAVL(root, data);
}
BinaryNode *insertAVL (BinaryNode *parent, int data) {
if (data < parent->getData()) {
if (parent->getLeft() != nullptr)
parent->setLeft(insertAVL(parent->getLeft(), data));
else
parent->setLeft(new BinaryNode(data));
return reBalance(parent);
}
else if (data > parent->getData()) {
if (parent->getRight()!= nullptr)
parent->setRight(insertAVL(parent->getRight(), data));
else
parent->setRight(new BinaryNode(data));
return reBalance(parent);
}
else
cout << "Error! 중복된 key" << endl;
return nullptr;
}
};'C | C++ > Data Structure & STL' 카테고리의 다른 글
| this.code(9).DS_ sort I. [heap, merge, quick]sort (0) | 2023.01.03 |
|---|---|
| this.code(8).DS_ Priority Queue. &. Heap (0) | 2023.01.03 |
| this.code(6).DS_ Tree, Binary Tree (0) | 2023.01.02 |
| this.code(5).DS_ List (4) | 2022.12.23 |
| this.code(4).DS_ Recursion (재귀)_최대공약수 (0) | 2022.10.30 |