introduction to algorithms(Thomas H. Cormen...) 의 수도코드를 강력하게 참고했습니다
node 구조체 구현
// node definition
typedef struct node{
int key;
struct node *parent;
struct node *left;
struct node *right;
} node_t
tree 초기화
// initialize root
node_t *root = NULL;
// insert nodes
insert(&root, 7);
insert(&root, 3);
insert(&root, 5);
insert(&root, 9);
// 7
// / \
// 3 9
// / \ | \
// N 5 N N
// / \
// N N
print_tree(root);
functions
int print_tree(node_t *curr) 함수
- 트리의 모든 노드의 key값을 오름차순으로 출력하는 함수
- recursion을 이용한 dfs
- left subtree 탐색 -> 현재 노드 출력 -> right subtree 탐색 순서
// print keys of tree in increasing order
// using dfs
int print_tree(node_t *curr){
// base case:
if (curr == NULL) return 0;
// recursive call: dfs
print_tree(curr->left);
printf("%d\n", curr->key);
print_tree(curr->right);
return 0;
}
node_t *search(node_t *curr, int k) 함수
- 주어진 key값을 가지는 노드를 찾아 그 주소(포인터) 반환하는 함수
- recursion을 이용한 탐색
- 주어진 key값과 노드의 key값을 비교해서 left child/ right child 노드로 이동
- 마지막 노드로 갔을때(주어진 key값이 없을 때)와 주어진 key값을 찾을 찾았을 때 탐색 종료
// find and return the address(node_t * type) of target node
// recursive version
node_t *search(node_t *curr, int k){
// base case1: end of tree: return NULL
if (curr == NULL){
printf("cannot find a node with value %d !!\n", k);
return curr;
}
// base case2: find target node
if (curr->key == k) return curr;
// target과 현재 노드의 key를 대소비교하며 찾아 내려간다
// search left-subtree
if (k < curr->key) return search(curr->left, k);
// search right-subtree
else return search(curr->right, k);
}
node_t *search_iterative(node_t *curr, int k) 함수
- 바로 위 search 함수의 iterative 버전
// find and return the address(node_t * type) of target node
// iterative version
node_t *search_iterative(node_t *curr, int k){
// move to child node
while (curr != NULL && curr->key != k){
// search left-subtree
if (k < curr->key) curr = curr->left;
// search right-subtree
else curr = curr->right;
}
// end of tree
if (curr == NULL){
printf("cannot find a node with value %d !!\n", k);
}
return curr;
}
node_t * minimum(node_t *curr) 함수
- 트리에서 최소 key값을 가지는 노드의 주소(포인터)를 반환하는 함수
- 트리에서 가장 왼쪽에 있는 노드를 반환
// find minimum key in tree
node_t * minimum(node_t *curr){
// move to most-left-outside node
while (curr->left != NULL) curr = curr->left;
return curr;
}
node_t *maximum(node_t *curr) 함수
- 트리에서 최대 key값을 가지는 노드의 주소(포인터)를 반환하는 함수
- 트리에서 가장 오른쪽에 있는 노드를 반환
// find maximum key in tree
node_t *maximum(node_t *curr){
// move to most-right-outside node
while (curr->right != NULL) curr = curr->right;
return curr;
}
node_t *successor(node_t *curr) 함수
- 주어진 노드의 successor 노드의 주소(포인터)를 반환하는 함수
- successor: 노드의 key들을 오름차순 정렬했을때 바로 다음에 오는 key값을 가지는 노드
- case1, 오른쪽 subtree가 비지 않았을 때: 오른쪽 subtree에서의 최소 값을 가지는 노드가 successor
- case2, 오른쪽 subtree가 비었을 때, curr의 조상 중 처음으로 left-child가 되는 노드의 부모 노드가 successor
// return the successor of given node
// successor: 주어진 노드의 key 바로 다음에 오는 key값을 가진 node
node_t *successor(node_t *curr){
// case1: right subtree is non-empty
if (curr->right != NULL) return minimum(curr->right);
// case2: right-subtree is empty
node_t *temp;
temp = curr->parent;
// 조건을 만족할 때까지 트리를 타고 올라간다
// 조건: curr의 조상 중 처음으로 left child가 되는 노드의 부모 노드를 찾는다
while( temp != NULL && temp->right == curr){
curr = temp;
temp = temp->parent;
}
// check impossible cases(루트노드까지 올라간 경우)
if (temp == NULL){
printf("there is no successor of given node!\n");
}
return temp;
}
node_t *predecessor(node_t *curr) 함수
- 주어진 노드의 predecessor 노드의 주소(포인터)를 반환하는 함수
- predecessor: 노드의 key들을 오름차순 정렬했을 때 직전에 오는 key값을 가지는 노드
- successor함수와 거울 대칭으로 탐색
// 참고:successor함수와 대칭
// return the predecessor of given node
// predecessor: 주어진 노드의 key 직전에 오는 key값을 가진 node
node_t *predecessor(node_t *curr){
// case1: left-subtree is non-empty
if (curr->left != NULL) return maximum(curr->left);
// case2: left-subtree is empty
node_t *temp;
temp = curr->parent;
// 조건을 만족할 때까지 트리를 타고 올라간다
// 조건: curr의 조상 중 처음으로 right-child가 되는 노드의 부모를 찾는다
while(temp != NULL && temp->left == curr){
curr = temp;
temp = temp->parent;
}
// check impossible cases
if (temp == NULL){
printf("there is no successor of given node!\n");
}
return temp;
}
int insert(node_t **ptr_root, int k) 함수
- 트리에 주어진 key값을 가지는 새로운 노드를 추가하는 함수
- 예외: 트리가 비었을 경우 새로운 노드를 root노드로 설정
- 주어진 key값과 현재 노드의 key값을 대소비교하면서 트리를 타고 내려간다
- leaf node에 도달하면 여기에 새로운 노드를 자식 노드로 추가
// 주어진 값을 갖는 노드 추가
int insert(node_t **ptr_root, int k){
// make new_node with key k
node_t * new_node = (node_t*)malloc(sizeof(node_t));
new_node->key = k;
new_node->parent = NULL;
new_node->left = NULL;
new_node->right = NULL;
// check tree is empty: make root points to new node
if (*ptr_root == NULL){
*ptr_root = new_node;
return 0;
}
// 대소비교하면서 leaf node까지 내려간다
node_t *curr = *ptr_root; // root부터 시작
node_t *before = NULL; // x 직전 node기록하기 위함
while (curr != NULL){ // before이 new_node의 부모가 될 노드
before = curr;
if (k < curr->key) curr = curr->left;
else curr = curr->right;
}
// curr == NULL 이면 before은 마지막 leaf node
// before node 밑에 new_node 추가
new_node->parent = before;
if (k < before->key) before->left = new_node;
else before->right = new_node;
return 1;
}
void delete(node_t **ptr_root, node_t *target) 함수
- 트리에서 주어진 노드를 삭제하는 함수
- 3가지 케이스로 나누어 삭제를 진행
- case1, target node의 자식 노드가 0개: target node 제거하고 그 위치에 NULL 추가
- case2, target node의 자식 노드가 1개: target node 제거 후 target node의 부모에 target node의 자식 노드 연결
- case3, target node의 자식 노드가 2개: target node와 그 successor의 key값을 교환하고, successor node를 제거(successor노드의 부모노드와 successor노드의 자식노드를 연결)
// target 노드의 주소값을 받아 트리에서 제거
void delete(node_t **ptr_root, node_t *target){
// introduction to algorithms 책 보고 이해하는 것 추천
////////////////////////
// 1. splice 대상 y 결정
node_t *y = NULL;
// target의 자식 노드가 0, 1개인 경우: splice 대상 y는 target 자신
if (target->left == NULL || target->right ==NULL) y = target;
// target의 자식 노드가 2개인 경우: splice 대상 y는 target 노드의 successor 노드
else y = successor(target);
/////////////////////////
// 2. y의 자식 노드 x 결정
// y가 잘려나가면 그 밑의 노드를 이어주어야 하므로
node_t *x = NULL;
if (y->left != NULL) x = y->left;
else x = y->right;
/////////////////////////
// 3. splicing y
// exception case1: x = NULL인 경우 제외
if (x != NULL) x->parent = y->parent;
// exception case2: y가 root node인 경우(y->parent == NULL)
if (y->parent == NULL) *ptr_root = x;
// y가 root node가 아닌 경우
else {
// y의 위치에 따라 x의 부모를 y의 부모로 설정
if (y->parent->left == y) y->parent->left = x;
else y->parent->right = x;
}
// target의 자식이 2개인 경우: splicing 대상 y는 target이 아니라 target의 successor
if (y != target) target->key = y->key;
// delete y
free(y);
}