균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1 2 4 44 17 78 1 2 32 50 1 1 48 62 3 88 1 n example of an VL tree (heights are shown next to the nodes) ch10-32
Tri-node Restructuring height height of leaf node : 1 height of inner node: 1 + MX (height of left child, height of right child) height difference height difference = height of left child height of right child tri-node restructuring re-arrange three node so that the re-arranged subtree has height difference less than or equal to 1 diff 3 diff -3 diff -1 diff -1 (Example 1) ch10-33 (Example 2)
Tri-node Restructuring rotate_ll (1) Single rotation LL of subtree diff 2 ch10-34
Tri-node Restructuring rotate_ll (2) c = z a = x b = y T 3 rotate_ll() a = x T 0 T 1 b = y c = z T 2 T 0 T 2 T 3 T 1 ch10-35
Tri-node Restructuring rotate_rr (1) Single rotation RR of subtree diff -2 diff -1 ht 0 ch10-36
Tri-node Restructuring rotate_rr (2) a = z T 0 b = y c = x rotate_rr() a = z b = y c = x T 1 T 2 T 3 T 0 T 1 T 2 T 3 ch10-37
Tri-node Restructuring rotate_lr (1) Double rotation LR of subtree diff -1 diff 2 ch10-38
Tri-node Restructuring rotate_lr (2) c= z a = y b= x T 3 rotate_lr() a = y b = x c = z T 0 T 1 T 0 T 1 T 2 T 3 T 2 ch10-39
Tri-node Restructuring rotate_rl (1) Double rotation RL of subtree diff -2 ch10-40
Tri-node Restructuring rotate_rl (2) a = z T 0 b= x c= y rotate_rl() a = z b = x c = y T 3 T 2 T 1 T 2 T 0 T 1 T 3 ch10-41
lgorithm getheight() lgorithm getheight(treenode* ptn) height = 0; if (ptn!= NULL) height = 1 + max (getheight(ptn->pl), getheight(ptn->pr); return height; end lgorithm getheightdiff() lgorithm getheightdiff(treenode* ptn) heightdiff = 0; if (ptn == NULL) return 0; heightdiff = getheight(ptn->pl) - getheight(ptn->pr); return heightdiff; end ch10-42
lgorithm realance() lgorithm realance(treenode** pptn) heightdiff = getheightdiff(*pptn); if (heightdiff > 1) // left sub-tree is higher if (getheightdiff(*pptn->pl) > 0) *pptn = rotate_ll(*pptn); else *pptn = rotate_lr(*pptn); else if (heightdiff < -1) // right sub-tree is higher if (getheightdiff(*pptn->pr) < 0) *pptn = rotate_rr(*pptn); else *pptn = rotate_rl(*pptn); return *pptn; end ch10-43
lgorithm rotate_ll() lgorithm rotate_ll(treenode* pparent) TreeNode* phild; phild = pparent->pl; pparent->pl = phild->pr; phild->pr = pparent; return phild; end cl c cr b br a b rotate_ll() c a ar cl cr br ar diff 2 D rotate_ll() D h ch10-44
lgorithm rotate_rr(), lgorithm rotate_rr(treenode* pparent) TreeNode* phild; phild = pparent->pr; pparent->pr = phild->pl; phild->pl = pparent; return phild; end al a bl b cl c b rotate_rr() a c al bl cl cr cr diff -2 D rotate_rr() h D ch10-45
lgorithm rotate_lr() lgorithm rotate_lr(treenode* pparent) TreeNode* phild; a rotate_lr() c phild = pparent->pl; pparent->pl = rotate_rr(phild); return rotate_ll(pparent); end bl b cl c cr ar b a bl cl cr ar diff -1 diff -1 h 4 diff 3 E D setleft(rotate_rr()) h 4 diff 3 D E rotate_ll() D E ch10-46
lgorithm rotate_rl() lgorithm rotate_rl(treenode* pparent) TreeNode* phild; a rotate_rl() c phild = pparent->pr; pparent->pr = rotate_ll(phild); al c b a b return rotate_rr(pparent); end cl cr br al cl cr br h 4 diff -3 D setright(rotate_ll( )) E h 4 diff -3 diff -1 D diff -1 E rotate_rr( ) diff -1 D diff -1 E ch10-47
/* inary Tree with Rebalancing (1) */ #include <stdio.h> #include <stdlib.h> #define Element int typedef struct TreeNode { Element data; TreeNode *pl; TreeNode *pr; }TreeNode; int getheight(treenode *ptn); int getheightdiff(treenode *ptn); TreeNode *rotate_ll(treenode* pparent); TreeNode *rotate_rr(treenode* pparent); TreeNode *rotate_lr(treenode* pparent); TreeNode *rotate_rl(treenode* pparent); TreeNode *realance(treenode **pptn); TreeNode *insertwithoutrebalancing(treenode **pptn, Element elm); TreeNode *insertwithrebalancing(treenode **pptn, Element elm); void printelement(element elm); void printtreeinorder(treenode *ptn); void printtreeinorderylevel(treenode *ptn, int level); void fprinttreeinorderylevel(file *fout, TreeNode *ptn, int level); void deletellnodes(treenode *ptn); ch10-48
/* inary Tree with Rebalancing (2) */ #define NUM_DT 10 void main() { FILE *fout; TreeNode *proot1 = NULL; TreeNode *proot2 = NULL; int data[num_dt] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; fout = fopen("output.txt", "w"); if (fout == NULL) { printf("error in opening output.txt file!!"); exit; } for (int i = 0; i < NUM_DT; i++) { proot1 = insertwithoutrebalancing(&proot1, data[i]); fprintf(fout, "fter insert (%d) into inary Tree with Rebalancing: ", data[i]); fprinttreeinorderylevel(fout, proot1, 0); fprintf(fout, " n"); } deletellnodes(proot1); ch10-49
/* inary Tree with Rebalancing (3) */ } for (int i = 0; i < NUM_DT; i++) { proot2 = insertwithrebalancing(&proot2, data[i]); fprintf(fout, "fter insert (%d) into inary Tree with Rebalancing: ", data[i]); fprinttreeinorderylevel(fout, proot2, 0); fprintf(fout, " n"); } deletellnodes(proot2); fclose(fout); void deletellnodes(treenode *ptn) { if (ptn == NULL) return; else { deletellnodes(ptn->pl); deletellnodes(ptn->pr); free(ptn); return; } } ch10-50
void fprinttreeinorderylevel(file *fout, TreeNode *ptn, int level) { TreeNode* phild = NULL; if (ptn!= NULL) { if (level == 0) fprintf(fout, " nroot (data: "); fprintf(fout, "%2d", ptn->data); fprintf(fout, ") n"); phild = ptn->pl; for (int i = 0; i<level; i++) fprintf(fout, " "); if (phild!= NULL) { fprintf(fout, "L (data: "); fprinttreeinorderylevel(fout, phild, level + 1); } else { fprintf(fout, "L (NULL) n"); } } } phild = ptn->pr; for (int i = 0; i<level; i++) fprintf(fout, " "); if (phild!= NULL) { fprintf(fout, "R (data: "); fprinttreeinorderylevel(fout, phild, level + 1); } else { fprintf(fout, "R (NULL) n"); } ch10-51
Result of insertwithoutrebalancing() ch10-52
Intermediate Results of insertwithrebalancing() ch10-53
Homework 10 10.1 동적메모리할당의이진트리 (inary tree) 를기반으로한 Galaxy 구현 (1) 별 (star) 의정보를관리하기위한구조체 struct Star 를정의하라. struct Star 에는 string 타입의이름 (char name[16]), integer 타입의 id (identifier) 와 age 가있고, double 데이터타입의 distance, luminosity, mass, radius 가있다. (2) 함수 Star * genstar() 는하나의 star 를동적으로생성하며, star 의데이터멤버들을랜덤함수를사용하여임의의값으로초기화한후, 생성된 star 의주소를반환한다. starid 는중복되지않는값으로지정되어야하며, starname 은알파벳 a ~ z 5 ~ 10 자로구성된다. 데이터멤버 distance, luminosity, mass, radius 및 age 는 10.0 ~ 10000.0 범위의값을임의로가진다. (3) 함수 printstar(star *ps) 는구성된 Galaxy 에포함된 star 들의 starname, starid 를순서대로 ( 첫번째 (head) 노드부터마지막 (tail) 노드까지 ) 출력한다. (4) Star 들을관리하기위한이진트리를구현하라. 이진트리를구성하기위한구조체 TreeNode 는왼쪽자식과오른쪽자식을각각가리키기위한두개의포인터를가지며, 구조체 star 노드를가리키기위한포인터 Star *ps 를가진다. (5) 함수 void * insertwithrebalancing(treenode **ppt, Star *ps) 는이진트리의이중포인터 (TreeNode **ppt) 와추가될 star 노드의주소 (Star *ps ) 를전달받고, tree node 를동적으로생성하며, 생성된노드를이진트리내의올바른위치 (starid 의오름차순으로정렬되는 ) 에삽입하고, 필요에따라 tri-node restructuring (balancing) 을실행한다. ch10-54
(6) 함수 void printtreeinorder(treenode *pt) 는이진트리에포함된 star들을 inorder 순회 방식으로출력한다. 출력되는 star들은 starid값이오름차순으로정렬되어있어야한다. (7) 함수 Star *searchtree(treenode *pt, int starid) 는이진탐색트리에포함된 star 중에서지정된 starid값을가지는트리노드를찾아, 그트리노드의주소를반환한다. (8) genstar() 함수를사용하여 20개의 star들을동적으로생성하고, inserttreenode() 함수를사용하여이진탐색트리에차례로추가하라. 이렇게구성된이진탐색트리는 starid 값에따라오름차순으로정렬되어있어야한다. (9) 이진탐색트리를 in-order 순회 에따라출력하라. (10) searchtree() 함수를사용하여, starid값을가지는트리노드를탐색하고, 해당 star의다른데이터 (starname, distance, luminosity, mass, radius 및 age) 를출력하라. ch10-55