RB트리는 AVL과 다르게 색상이라는 속성과 그 속성을 이용하여
트리의 레벨 균형을 맞추는 BST트리의 한 종류이다.
BST트리중 균형을 잡는 트리는 대표적으로 2개가 있다.
RB트리와 AVL트리이다.
두 트리의 차이는 아래와 같다.
RB트리 vs AVL
| RB 트리 | AVL 트리 | |
| 이진 탐색 트리인가? | yes | yes |
| 삽입/삭제/검색 시간 | worst case = O(log n) | worst case = O(log n) |
| 삽입 /삭제 | AVL 보다 빠름 | RB보다 느림 |
| 검색 | AVL 보다 느림 | RB보다 빠름 |
| balance 방식 | black - depth | balance-factor |
| 응용사례 | 커널,자바 Tree map,c++ map | dictionary,검색용도 |
AVL
사진 출처: https://en.wikipedia.org/wiki/AVL_tree
AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로 발명되었다. AVL 트리에서, 두 자식 서브트리의 높이는 항상 최대 1만큼 차이난다. 만약 어떤 시점에서 높이 차이가 1보다 커지면 이 속성을 유지하기 위해서 스스로 균형을 잡는다. 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(log n)의 시간복잡도가 걸린다. 삽입과 삭제는 한 번 이상의 트리 회전을 통해 균형을 잡을 수 있다.
출처 : https://ko.wikipedia.org/wiki/AVL_%ED%8A%B8%EB%A6%AC
AVL 트리 - 위키백과, 우리 모두의 백과사전
위키백과, 우리 모두의 백과사전. 컴퓨터 과학에서 AVL 트리(발명자의 이름인 Adelson-Velsky and Landis에서 따온 이름)는 자가 균형 이진 탐색 트리이다. 스스로 균형을 잡는 데이터 구조 중 처음으로
ko.wikipedia.org
AVL은 단순하게 트리의 레벨 차이를 보면서 Rebalance를 잡는 트리이다.
밸런스를 다시잡는 이유는 트리의 구조가 편향적이면 worst case에서 시간이 O(n)이 나오기 때문에
트리를 이용하는 이유가 없어져서 이다.
간단하게보는 AVL
사진 출처 : https://en.wikipedia.org/wiki/AVL_tree
동작 방식은 대충 위와 같고
구현은 아래와 같다.
AVL 트리 구현
#include <stdio.h>
#include <stdlib.h>
void BSTMakeAndInit(BTreeNode ** pRoot)
{
*pRoot = NULL;
}
BSTData BSTGetNodeData(BTreeNode * bst)
{
return GetData(bst);
}
BTreeNode * BSTInsert(BTreeNode ** pRoot, BSTData data) {
if(*pRoot == NULL) {
*pRoot = MakeBTreeNode();
SetData(*pRoot, data);
}
else if(data < GetData(*pRoot)) {
BSTInsert(&((*pRoot)->left), data);
*pRoot = Rebalance(pRoot);
}
else if(data > GetData(*pRoot)) {
BSTInsert(&((*pRoot)->right), data);
*pRoot = Rebalance(pRoot);
}
else {
return NULL; // 키의 중복을 허용하지 않는다.
}
return *pRoot;
}
BTreeNode * BSTSearch(BTreeNode * bst, BSTData target)
{
BTreeNode * cNode = bst; // current node
BSTData cd; // current data
while(cNode != NULL)
{
cd = GetData(cNode);
if(target == cd)
return cNode;
else if(target < cd)
cNode = GetLeftSubTree(cNode);
else
cNode = GetRightSubTree(cNode);
}
return NULL;
}
BTreeNode * BSTRemove(BTreeNode ** pRoot, BSTData target)
{
// 삭제 대상이 루트 노드인 경우를 별도로 고려해야 한다.
BTreeNode * pVRoot = MakeBTreeNode(); // 가상 루트 노드;
BTreeNode * pNode = pVRoot; // parent node
BTreeNode * cNode = *pRoot; // current node
BTreeNode * dNode; // delete node
// 루트 노드를 pVRoot가 가리키는 노드의 오른쪽 서브 노드가 되게 한다.
ChangeRightSubTree(pVRoot, *pRoot);
// 삭제 대상을 저장한 노드 탐색
while(cNode != NULL && GetData(cNode) != target)
{
pNode = cNode;
if(target < GetData(cNode))
cNode = GetLeftSubTree(cNode);
else
cNode = GetRightSubTree(cNode);
}
if(cNode == NULL) // 삭제 대상이 존재하지 않는다면,
return NULL;
dNode = cNode; // 삭제 대상을 dNode가 가리키게 한다.
// 첫 번째 경우: 삭제할 노드가 단말 노드인 경우
if(GetLeftSubTree(dNode) == NULL && GetRightSubTree(dNode) == NULL)
{
if(GetLeftSubTree(pNode) == dNode)
RemoveLeftSubTree(pNode);
else
RemoveRightSubTree(pNode);
}
// 두 번째 경우: 하나의 자식 노드를 갖는 경우
else if(GetLeftSubTree(dNode) == NULL || GetRightSubTree(dNode) == NULL)
{
BTreeNode * dcNode; // delete node의 자식 노드
if(GetLeftSubTree(dNode) != NULL)
dcNode = GetLeftSubTree(dNode);
else
dcNode = GetRightSubTree(dNode);
if(GetLeftSubTree(pNode) == dNode)
ChangeLeftSubTree(pNode, dcNode);
else
ChangeRightSubTree(pNode, dcNode);
}
// 세 번째 경우: 두 개의 자식 노드를 모두 갖는 경우
else
{
BTreeNode * mNode = GetRightSubTree(dNode); // mininum node
BTreeNode * mpNode = dNode; // mininum node의 부모 노드
int delData;
// 삭제할 노드를 대체할 노드를 찾는다.
while(GetLeftSubTree(mNode) != NULL)
{
mpNode = mNode;
mNode = GetLeftSubTree(mNode);
}
// 대체할 노드에 저장된 값을 삭제할 노드에 대입한다.
delData = GetData(dNode); // 대입 전 데이터 백업
SetData(dNode, GetData(mNode));
// 대체할 노드의 부모 노드와 자식 노드를 연결한다.
if(GetLeftSubTree(mpNode) == mNode)
ChangeLeftSubTree(mpNode, GetRightSubTree(mNode));
else
ChangeRightSubTree(mpNode, GetRightSubTree(mNode));
dNode = mNode;
SetData(dNode, delData); // 백업 데이터 복원
}
// 삭제된 노드가 루트 노드인 경우에 대한 처리
if(GetRightSubTree(pVRoot) != *pRoot)
*pRoot = GetRightSubTree(pVRoot);
free(pVRoot);
*pRoot = Rebalance(pRoot); // 노드 제거 후 리밸런싱!
return dNode;
}
void ShowIntData(int data)
{
printf("%d ", data);
}
void BSTShowAll(BTreeNode * bst)
{
InorderTraverse(bst, ShowIntData);
}
BTreeNode * MakeBTreeNode(void)
{
BTreeNode * nd = (BTreeNode*)malloc(sizeof(BTreeNode));
nd->left = NULL;
nd->right = NULL;
return nd;
}
BTData GetData(BTreeNode * bt)
{
return bt->data;
}
void SetData(BTreeNode * bt, BTData data)
{
bt->data = data;
}
BTreeNode * GetLeftSubTree(BTreeNode * bt)
{
return bt->left;
}
BTreeNode * GetRightSubTree(BTreeNode * bt)
{
return bt->right;
}
void MakeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
if(main->left != NULL)
free(main->left);
main->left = sub;
}
void MakeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
if(main->right != NULL)
free(main->right);
main->right = sub;
}
void PreorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if(bt == NULL)
return;
action(bt->data);
PreorderTraverse(bt->left, action);
PreorderTraverse(bt->right, action);
}
void InorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if(bt == NULL)
return;
InorderTraverse(bt->left, action);
action(bt->data);
InorderTraverse(bt->right, action);
}
void PostorderTraverse(BTreeNode * bt, VisitFuncPtr action)
{
if(bt == NULL)
return;
PostorderTraverse(bt->left, action);
PostorderTraverse(bt->right, action);
action(bt->data);
}
BTreeNode * RemoveLeftSubTree(BTreeNode * bt)
{
BTreeNode * delNode;
if(bt != NULL) {
delNode = bt->left;
bt->left = NULL;
}
return delNode;
}
BTreeNode * RemoveRightSubTree(BTreeNode * bt)
{
BTreeNode * delNode;
if(bt != NULL) {
delNode = bt->right;
bt->right = NULL;
}
return delNode;
}
void ChangeLeftSubTree(BTreeNode * main, BTreeNode * sub)
{
main->left = sub;
}
void ChangeRightSubTree(BTreeNode * main, BTreeNode * sub)
{
main->right = sub;
}
// LL 회전
BTreeNode * RotateLL(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetLeftSubTree(pNode);
ChangeLeftSubTree(pNode, GetRightSubTree(cNode));
ChangeRightSubTree(cNode, pNode);
return cNode;
}
// RR 회전
BTreeNode * RotateRR(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetRightSubTree(pNode);
ChangeRightSubTree(pNode, GetLeftSubTree(cNode));
ChangeLeftSubTree(cNode, pNode);
return cNode;
}
// RL 회전
BTreeNode * RotateRL(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetRightSubTree(pNode);
ChangeRightSubTree(pNode, RotateLL(cNode)); // 부분적 LL 회전
return RotateRR(pNode); // RR 회전
}
// LR 회전
BTreeNode * RotateLR(BTreeNode * bst)
{
BTreeNode * pNode;
BTreeNode * cNode;
pNode = bst;
cNode = GetLeftSubTree(pNode);
ChangeLeftSubTree(pNode, RotateRR(cNode)); // 부분적 RR 회전
return RotateLL(pNode); // LL 회전
}
// 트리의 높이를 계산하여 반환
int GetHeight(BTreeNode * bst)
{
int leftH; // left height
int rightH; // right height
if(bst == NULL)
return 0;
// 왼쪽 서브 트리 높이 계산
leftH = GetHeight(GetLeftSubTree(bst));
// 오른쪽 서브 트리 높이 계산
rightH = GetHeight(GetRightSubTree(bst));
// 큰 값의 높이를 반환한다.
if(leftH > rightH)
return leftH + 1;
else
return rightH + 1;
}
// 두 서브 트리의 높이의 차를 반환
int GetHeightDiff(BTreeNode * bst)
{
int lsh; // left sub tree height
int rsh; // right sub tree height
if(bst == NULL)
return 0;
lsh = GetHeight(GetLeftSubTree(bst));
rsh = GetHeight(GetRightSubTree(bst));
return lsh - rsh;
}
// 트리의 균형을 잡는다.
BTreeNode * Rebalance(BTreeNode ** pRoot)
{
int hDiff = GetHeightDiff(*pRoot);
if(hDiff > 1) // 왼쪽 서브 트리 방향으로 높이가 2 이상 크다면
{
if(GetHeightDiff(GetLeftSubTree(*pRoot)) > 0)
*pRoot = RotateLL(*pRoot);
else
*pRoot = RotateLR(*pRoot);
}
if(hDiff < -1) // 오른쪽 서브 트리 방향으로 2 이상 크다면
{
if(GetHeightDiff(GetRightSubTree(*pRoot)) < 0)
*pRoot = RotateRR(*pRoot);
else
*pRoot = RotateRL(*pRoot);
}
return *pRoot;
}
int main(void)
{
BTreeNode * avlRoot;
BTreeNode * clNode; // current left node
BTreeNode * crNode; // current right node
BTreeNode * clNode2;
BTreeNode * crNode2;
BTreeNode * clNode3;
BTreeNode * crNode3;
BSTMakeAndInit(&avlRoot);
BSTInsert(&avlRoot, 1);
BSTInsert(&avlRoot, 2);
BSTInsert(&avlRoot, 3);
BSTInsert(&avlRoot, 4);
BSTInsert(&avlRoot, 5);
BSTInsert(&avlRoot, 6);
BSTInsert(&avlRoot, 7);
BSTInsert(&avlRoot, 8);
BSTInsert(&avlRoot, 9);
printf("루트 노드: %d \n", GetData(avlRoot)); //4
clNode = GetLeftSubTree(avlRoot); //2, 루트 4의 왼편
crNode = GetRightSubTree(avlRoot); //6, 루트 4의 오른편
printf("%d, %d \n", GetData(clNode), GetData(crNode));
clNode2 = GetLeftSubTree(clNode); //1, 2의 왼편
crNode2 = GetRightSubTree(clNode); //3, 2의 오른편
printf("%d, %d \n", GetData(clNode2), GetData(crNode2));
clNode2 = GetLeftSubTree(crNode); //5, 3의 왼편
crNode2 = GetRightSubTree(crNode); //8, 3의 오른편
printf("%d, %d \n", GetData(clNode2), GetData(crNode2));
clNode3 = GetLeftSubTree(crNode2); //7, 8의 왼편
crNode3 = GetRightSubTree(crNode2); //9, 8의 오른편
printf("%d, %d \n", GetData(clNode3), GetData(crNode3));
return 0;
}
RB트리
RB트리에 대해서는 영어 wikipedia가 그렇게 잘나와 있다고 해서 원문판으로 보는걸 추천한다고 한다 ㅠ....
a red–black tree is a specialised binary search tree data structure noted for fast storage and retrieval of ordered information, and a guarantee that operations will complete within a known time. Compared to other self-balancing binary-search-tree, the nodes in a red-black tree hold an extra bit called "color" representing "red" and "black" which is used when re-organising the tree to ensure that it is always approximately balanced.
When the tree is modified, the new tree is rearranged and "repainted" to restore the coloring properties that constrain how unbalanced the tree can become in the worst case. The properties are designed such that this rearranging and recoloring can be performed efficiently.
The (re-)balancing is not perfect, but guarantees searching in Big_O time of (log n), where
is the number of entries (or keys) in the tree. The insert and delete operations, along with the tree rearrangement and recoloring, are also performed in (log n) time.
영어라 굉장히 어렵긴한데 대충 보면
RB트리는 안에 내용을 검색, 작업하는데 빠른 시간을 보장하는 특수한 BST 자료구조이고, 레드와 블랙이라는 색상의 속성을 추가해서 색상 변경을 하여 트리를 재구성(밸런싱)을 한다.
밸런싱 잡는 것이 완벽하지는 않지만 이런 다시 재배치하는속성은 Big _O의 시간을 보장한다.
한번 아래에서 구현 해보자
RB트리 구현
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
typedef enum { RBTREE_RED, RBTREE_BLACK } color_t;
typedef int key_t;
typedef struct node_t {
color_t color;
key_t key;
struct node_t *parent, *left, *right;
} node_t;
typedef struct {
node_t *root;
node_t *nil; // for sentinel
} rbtree;
rbtree *new_rbtree(void);
void delete_rbtree(rbtree *);
node_t *rbtree_insert(rbtree *, const key_t);
node_t *rbtree_find(const rbtree *, const key_t);
node_t *rbtree_min(const rbtree *);
node_t *rbtree_max(const rbtree *);
int rbtree_erase(rbtree *, node_t *);
int rbtree_to_array(const rbtree *, key_t *, const size_t);
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *)calloc(1, sizeof(rbtree));
// TODO: initialize struct if needed
p->nil = (node_t *)calloc(1,sizeof(node_t));
p->root = p->nil;
p->nil->color = RBTREE_BLACK;
return p;
}
void postorder(rbtree *t,node_t *delete_node){
if(delete_node == NULL || delete_node == t->nil){
return;
}
postorder(t,delete_node->right);
postorder(t,delete_node->left);
if(delete_node != NULL){
free(delete_node);
}
}
void delete_rbtree(rbtree *t) {
// TODO: reclaim the tree nodes's memory
postorder(t,t->root);
free(t->nil);
free(t);
}
void rotate_left(rbtree *t,node_t *x){
node_t *y = x->right; // 현재노드의 오른쪽 노드 포인터
x->right = y->left; // 왼쪽으로 돌리는것. 돌리는 노드 자식 왼쪽 노드가 기존 노드의 오른쪽에 붙는다.
if (y->left != t->nil) { // 원래 자손노드가 닐노드가 아니면
y->left->parent = x; // 위치 로테이션
}
y->parent = x->parent; // 조상 갱신
if (x->parent == t->nil){
t->root = y;
}
else if(x == x->parent->left) { // 위에서 처리 못한 x 노드도 붙여준다.
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// 왼쪽 함수와 반대로 돌기
void rotate_right(rbtree *t,node_t *y){
node_t *x = y->left;
y->left = x->right;
// 왼쪽
if (x->right != t->nil) {
x->right->parent = y;
}
//
x->parent = y->parent;
if (y->parent == t->nil) {
t->root = x;
}
else if(y == y->parent->right) {
y->parent->right = x;
}
else {
y->parent->left = x;
}
x->right = y;
y->parent = x;
}
// 삽입 밸런스 팩터
void insert_fixup(rbtree* t,node_t *z){
// 함수 실행전 불변식은 3가지
// 1. 노드 z는 RED이다.
// 2. z의 부모가 루트면 z의 부모는 Black
// 3. 레드 블랙트리의 특성 위반의 경우 1가지만 위반하는 경우는 2,4의 특성이다. 2가 위반되면 z가 루트이고 적색이고 4가 위반되면 z와 z의 부모가 모두 적색이다.
while (z->parent->color == RBTREE_RED){
// 가족(결합)이면 진행한다.
if (z->parent == z->parent->parent->left) {
node_t *y = z->parent->parent->right;
if (y->color == RBTREE_RED) { // Case 1 삼촌 노드가 적색인경우
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
else{
if(z == z->parent->right){ // Case 2 삼촌 y가 흑색이며, z가 오른쪽 자식인 경우
z = z->parent;
rotate_left(t,z);
}
z->parent->color = RBTREE_BLACK; // Case 3 삼촌 y가 흑색이며, z가 왼쪽 자식인 경우
z->parent->parent->color = RBTREE_RED;
rotate_right(t,z->parent->parent);
}
}
// 반대로수행
else{
node_t *y = z->parent->parent->left;
if (y->color == RBTREE_RED) {
z->parent->color = RBTREE_BLACK;
y->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
z = z->parent->parent;
}
else{
if(z == z->parent->left){
z = z->parent;
rotate_right(t,z);
}
z->parent->color = RBTREE_BLACK;
z->parent->parent->color = RBTREE_RED;
rotate_left(t,z->parent->parent);
}
}
}
t->root->color = RBTREE_BLACK;
}
// 삽입
node_t *rbtree_insert(rbtree *t, const key_t key) {
node_t *z = (node_t *)calloc(1,sizeof(node_t));
z->key = key;
node_t *y = t->nil;
node_t *x = t->root;
// 크기를 확인하고 왼쪽 오른쪽
while (x != t->nil){
y = x;
if (z->key < x->key){
x = x->left;
}
else x = x->right;
}
z->parent = y;
if(y == t->nil){
t->root = z;
}
else if(z->key < y->key){
y->left = z;
}
else {
y->right = z;
}
z->left = t->nil;
z->right = t->nil;
z->color = RBTREE_RED;
insert_fixup(t,z);
return z;
}
node_t *rbtree_find(const rbtree *t, const key_t key) {
// TODO: implement find
// 탐색 노드를 하나 생성해서 루트 노드에서 부터 탐색
node_t *ptr = t->root;
while(ptr != t->nil && key != ptr->key){
if (key < ptr->key){
ptr = ptr->left;
}
else {
ptr = ptr->right;
}
}
if (ptr == t->nil) {
return NULL;
}
return ptr;
}
// 가장 작은 노드 반환
node_t *tree_minimum(node_t *x,node_t *nil){
while (x->left != nil){
x = x->left;
}
return x;
}
node_t *rbtree_min(const rbtree *t) {
// TODO: implement find
node_t *realy_min;
realy_min = tree_minimum(t->root,t->nil);
return realy_min;
}
// 가장 큰 노드 반환
node_t *rbtree_max(const rbtree *t) {
// TODO: implement find
node_t *realy_max = t->root;
while (realy_max->right != t->nil){
realy_max = realy_max->right;
}
return realy_max;
}
// 부모와 위치 변환 함수
void rb_transplant(rbtree *t,node_t *n1,node_t *n2) {
if(n1->parent == t->nil){
t->root = n2;
}
else if(n1 == n1->parent->left){
n1->parent->left = n2;
}
else {
n1->parent->right = n2;
}
n2->parent = n1->parent;
}
// 삭제 밸런스 팩터
void rb_delete_fixup(rbtree *t,node_t *x){
while (x != t->root && x->color == RBTREE_BLACK){
if(x == x->parent->left){
node_t *w = x->parent->right;
if(w->color == RBTREE_RED){
w->color = RBTREE_BLACK; // Case 1 x의 형제 w가 적색인 경우
x->parent->color = RBTREE_RED;
rotate_left(t,x->parent);
w = x->parent->right;
}
if (w->left->color == RBTREE_BLACK && w->right->color == RBTREE_BLACK){
w->color = RBTREE_RED; // Case2 x의 형제 w는 흑색이고 w의 두 자식이 모두 흑색인 경우
x = x->parent;
}
else{
if(w->right->color == RBTREE_BLACK){
w->left->color = RBTREE_BLACK; // Case3 x의 형제 w는 흑색w의 오니쪽 자식은 RED, w의 오른쪽 자식은 Black
w->color = RBTREE_RED;
rotate_right(t,w);
w = x->parent->right;
}
w->color = x->parent->color; // Case4 x의 형제 w는 흑색이고 w의 오른쪽 자식은 RED인 경우
x->parent->color = RBTREE_BLACK;
w->right->color = RBTREE_BLACK;
rotate_left(t,x->parent);
x = t->root;
}
}
else {
// 반대 상황일 때
node_t *w = x->parent->left;
if(w->color == RBTREE_RED){
w->color = RBTREE_BLACK;
x->parent->color = RBTREE_RED;
rotate_right(t,x->parent);
w = x->parent->left;
}
if (w->right->color == RBTREE_BLACK && w->left->color == RBTREE_BLACK){
w->color = RBTREE_RED;
x = x->parent;
}
else{
if(w->left->color == RBTREE_BLACK){
w->right->color = RBTREE_BLACK;
w->color = RBTREE_RED;
rotate_left(t,w);
w = x->parent->left;
}
w->color = x->parent->color;
x->parent->color = RBTREE_BLACK;
w->left->color = RBTREE_BLACK;
rotate_right(t,x->parent);
x = t->root;
}
}
}
x->color = RBTREE_BLACK;
}
// 삭제 함수
int rbtree_erase(rbtree *t, node_t *p) {
// TODO: implement erase
node_t *x;
node_t *y = p;
int orginal_color = y->color;
if(p->left == t->nil){
x = p->right;
rb_transplant(t,p,p->right); // 두 노드의 위치 변환
}
else if(p->right == t->nil){
x = p->left;
rb_transplant(t,p,p->left);
}
else{
y = tree_minimum(p->right,t->nil);
orginal_color = y->color;
x = y->right;
if(y->parent == p){
x->parent = y;
}
else{
rb_transplant(t,y,y->right);
y->right = p->right;
y->right->parent = y;
}
rb_transplant(t,p,y);
y->left = p->left;
y->left->parent = y;
y->color = p->color;
}
if (orginal_color == RBTREE_BLACK){
rb_delete_fixup(t,x);
}
free(p);
return 0;
}
// 중위순회 왼-> 오른쪽 탐색
void inorder(const rbtree *t,node_t *search, key_t *arr,int* index){
if (search == t->nil) return;
inorder(t,search->left,arr,index);
arr[(*index)++] = search->key;
printf("%d->",search->key);
inorder(t,search->right,arr,index);
}
// 배열 출력
int rbtree_to_array(const rbtree *t, key_t *arr, const size_t n) {
// TODO: implement to_array
node_t *search_node = t->root;
int *index = calloc(1,sizeof(int));
inorder(t,search_node,arr,index);
free(index);
return 0;
}
int main(int argc, char *argv[]) {
int flag = 1;
int data;
int cnt = 0;
int insertdata;
int searchnode;
int deletenode;
int treeprint[1000];
node_t *nodesearch;
printf("트리를 생성하시겠습니까?\n1. 생성\t2. 안함\n\n");
int seclect;
scanf("%d",&seclect);
rbtree *tree;
if (seclect == 1){
tree = new_rbtree();
}
else {
printf("종료하겠습니다.\n");
exit(1);
return 0;
}
printf("메뉴를 선택하시오\n");
while(flag) {
printf("\n\n============================================================================================\n");
printf("선택할 메뉴를 선택해주세요\n0. 종료\t 1. 삽입\t2. 노드 존재 탐색\t3. 삭제\t\t4. 노드 확인\n");
printf("============================================================================================\n\n");
scanf("%d",&data);
if (data == 0){
nodesearch = rbtree_find(tree,searchnode);
if (nodesearch != NULL){
printf("아직 남아있는 노드가 있습니다.\n");
}
else{
printf("종료하겠습니다.\n");
delete_rbtree(tree);
break;
}
}
switch (data)
{
case 1:
printf("삽입할 노드를 적어주세요\n");
scanf("%d",&insertdata);
rbtree_insert(tree,insertdata);
printf("%d 노드가 삽입되었습니다!\n",insertdata);
cnt++;
printf("\n\n\n");
break;
case 2:
printf("탐색할 노드를 입력하세요\n");
scanf("%d",&searchnode);
nodesearch = rbtree_find(tree,searchnode);
if (nodesearch == NULL){
printf("해당 노드가 없습니다.\n");
printf("\n\n\n");
break;
}
printf("탐색한 노드 => %d\n",nodesearch->key);
printf("%d번 노드가 존재합니다!\n",nodesearch->key);
printf("\n\n\n");
break;
case 3:
printf("삭제할 노드를 입력하세요\n");
printf("현재 노드 = ");
rbtree_to_array(tree,treeprint,cnt);
printf("\n\n");
scanf("%d",&deletenode);
nodesearch = rbtree_find(tree,deletenode);
printf("\n");
if (nodesearch == NULL) {
printf("%d 노드가 존재하지 않습니다!\n",deletenode);
}
else{
rbtree_erase(tree,nodesearch);
printf("%d 노드가 삭제되었습니다!\n",deletenode);
cnt--;
}
printf("\n\n\n");
break;
case 4:
if(cnt <= 0){
printf("노드가 없습니다!\n");
}
else{
rbtree_to_array(tree,treeprint,cnt);
}
printf("\n\n");
break;
default:
break;
}
}
return 0;
}
이번주는 진짜 머리 깨질뻔 했다...ㅋㅋㅋ
원래 알던 내용인데도 매일 밤새서 디버그만 잡아서 github 신경도 못쓴거 같다.
'정글' 카테고리의 다른 글
| TIL(20일차) 동적 메모리 할당 (0) | 2023.05.14 |
|---|---|
| TIL(19일차) 예외흐름 제어 (1) | 2023.05.13 |
| TIL(18일차) RB트리 삭제 (0) | 2023.05.10 |
| TIL(17일차) 레드블랙트리 삽입 (0) | 2023.05.08 |
| TIL(16일차) 포인터 디테일 (0) | 2023.05.07 |
