배상원
Binary Search Tree (BST) Balanced BSTs Red-Black Tree Splay Tree Geometric Search Trees Range Tree Interval Tree Segment Tree Binary Indexed Tree
Definition (recursive) An empty tree is a binary tree A tree with a root node whose left and right subtrees are binary trees is a binary tree level = 0 I level = 1 level = 2 A B F height = 3 J K L level = 3 E 4
Binary tree with BST property y in left subtree of x, then key[y] key[x]. y in right subtree of x, then key[y] key[x]. x A B E F I J K L y y 5
Linked data structure root(t) : pointer to root node of a BST T Each node contains fields: key left : pointer to left child (root of left subtree) right : pointer to right child (root of right subtree) p : pointer to parent. p[root[t]] = NIL (optional). key 6
Supports dynamic set operations Search Minimum Maximum Successor Predecessor Insert Delete 연산수행시간 : O(h) h : height of binary search tree h could be n in worst case 7
Inorder-Tree-Walk (x) 1. if x NIL 2. then Inorder-Tree-Walk(left[p]) 3. print key[x] 4. Inorder-Tree-Walk(right[p]) Running Time: O(n) A B E F I J K L A B E F I J K L 8
Tree-Search(x, k) 1. if x = NIL or k = key[x] 2. then return x 3. if k < key[x] 4. then return Tree-Search(left[x], k) 5. else return Tree-Search(right[x], k) Running Time: O(h) A B E F I J K L 9
Tree-Minimum(x) Tree-Maximum(x) 1. while left[x] NIL 1. while right[x] NIL 2. do x left[x] 2. do x right[x] 3. return x 3. return x A B E F I J K L 10
Successor of node x: node y such that key[y] is the smallest key that is greater than key[x] The successor of the largest key is NIL. Successor of B? Successor of F? A B E F I J K L 11
Two cases for searching If node x has a non-empty right subtree x s successor is the minimum in the right subtree of x. If node x has an empty right subtree y is the successor of x x is the predecessor of y x y y x Go up through right child pointers, and finally through one left child pointer 12
Tree-Successor(x) 1. if right[x] NIL 2. then return Tree-Minimum(right[x]) 3. y p[x] 4. while y NIL and x = right[y] 5. do x y 6. y p[y] 7. return y Running Time: O(h) 13
Symmetric to Successor 14
Tree-Insert(T, z) 1. y NIL 2. x root[t] A 3. while x NIL 4. do y x 5. if key[z] < key[x] 6. then x left[x] 7. right[x] else x 8. p[z] y 9. if y = NIL 10. then root[t] z 11. else if key[z] < key[y] 12. then left[y] z 13. else right[y] z B E I G J K F Running Time: O(h) L 15
3 Cases : Delete(T, x) case 1: x has no children Remove leaf node x case 2: x has one children Make p[x] point to child case 3: x has two children Swap x with its successor and perform case 1 or case 2 to delete it I delete F delete G delete B, I A B E G F J K L Running Time: O(h) 16
Red-Black Tree Splay Tree
Supports dynamic set operations Search, Minimum, Maximum, Successor, Predecessor Insert, Delete Binary Search Tree 연산수행시간 : O(h) h : height of binary search tree h can be n in worst case Balanced Binary Search Tree h = O(log n) always! 연산수행시간 : O(h) = O(log n) AVL Tree 2-3 Tree Red-Black Tree Splay Tree 18
Red-black tree (RBT) Binary search trees augmented with node color Operations designed to guarantee that the height h = O(log n) 19
A Red-Black Tree is a BST satisfying 5 Properties 1. Every node is either red or black 2. Every leaf (NULL pointer) is black Note: this means every real node has 2 children 3. If a node is red, then both children are black Note: there are no 2 consecutive reds on a path 4. Every path from a node to descendent leaf contains the same number of black nodes 5. The root is always black 20
Example 14 7 16 5 9 19 8 12 17 21 11 Property 1 Property 2 Property 3 Property 4 Property 5 By properties 3 and 4, the height of RBT is O(log n) 21
Operations Search, Minimum, Maximum, Predecessor, Successor O(log n) time Insertion, Deletion Restructure RBT to guarantee the height to be O(log n) 22
Color this tree: 7 7 5 9 12 RBT Properties 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 23
Insert 8 Where does it go? 7 5 9 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 24
Insert 8 Where does it go? 5 9 What color should it be? 8 12 7 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 25
Insert 8 Where does it go? 5 9 What color should it be? 8 12 7 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 26
Insert 11 Where does it go? 7 5 9 8 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 27
Insert 11 Where does it go? What color? 7 5 9 8 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 28
Insert 11 Where does it go? What color? 7 5 9 Can t be red! (#3) 8 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 29
Insert 11 Where does it go? What color? Can t be red! (#3) Can t be black! (#4) 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 7 5 9 8 11 12 30
Insert 11 Where does it go? What color? Solution: recolor the tree 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 7 5 9 8 11 12 31
Insert 10 Where does it go? 7 5 9 8 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 11 32
Insert 10 Where does it go? What color? 7 5 9 8 12 1. Every node is either red or black 2. Every leaf (NULL pointer) is black 3. If a node is red, both children are black 4. Every path from node to descendent leaf contains the same number of black nodes 5. The root is always black 10 11 33
Insert 10 Where does it go? What color? A: no color! Tree is too imbalanced Must change tree structure to allow recoloring Goal: restructure tree in O(log n) time 7 5 9 8 10 11 12 34
Rotation : Basic operation to restructure RBT y rightrotate(y) x A x B C leftrotate(x) A B y C Preserves the in-order property of BST 35
Example 7 5 9 8 leftrotate(9) rightrotate(12) 12 7 5 12 9 11 8 11 Preserves the inorder property of BST 36
Basic idea of Insertion Insert x into tree (as in BST) Color x red Only RBT Property 3 may be violated (if parent[x] is red) If so, move the violation up tree until a place is found where it can be fixed Total time will be O(log n) 37
rbinsert(x) treeinsert(x); x->color = RED; // Move violation of #3 up tree, maintaining #4 as invariant: while (x!=root && x->p->color == RED) if (x->p == x->p->p->left) // p(x) is left child of parent y = x->p->p->right; // y : uncle of x if (y->color == RED) x->p->color = BLACK; y->color = BLACK; x->p->p->color = RED; x = x->p->p; else // y->color == BLACK if (x == x->p->right) x = x->p; leftrotate(x); x->p->color = BLACK; x->p->p->color = RED; rightrotate(x->p->p); else // x->p == x->p->p->right (same as above, but with right & left exchanged) T.root->color = BLACK; Case 1: uncle is RED Case 2 Case 3 38
if (y->color == RED) x->p->color = BLACK; y->color = BLACK; x->p->p->color = RED; x = x->p->p; Case 1: Uncle y is red In figures below, all s are equal-black-height subtrees A C D y case 1 A C new x D B x B 39
40 C A D B C A D B x y new x case 1 B x C A D C A D y new x B x case 1
if (x == x->p->right) x = x->p; leftrotate(x); // continue with case 3 code Case 2: Uncle y is black Node x is a right child Transform to case 3 via a left-rotation A C y case 2 B C y B x A x 41
x->p->color = BLACK; x->p->p->color = RED; rightrotate(x->p->p); Case 3: Uncle y is black Node x is a left child Change colors; rotate right B C y case 3 x A B C A x 42
x is a left/right child of a parent Left child Right child Root cases Case 1 Case 2 Case 3 Symmetric hint Move the red color to a parent, and continue the loop Run case 2 and stop the loop Run case 3 and stop the loop Change the color to black 43
11 2 14 1 7 15 5 8 y 4 x case 1 44
11 2 14 y 1 7 x 15 5 8 4 case 2 45
11 7 14 y x 2 8 15 1 5 4 case 3 46
7 x 2 11 1 5 8 14 4 15 47
Basic idea to Deletion (rbdelete(t, z)) delete z from tree (as in TreeDelete(T, z) for BSTs) Let y be the node that has actually been deleted and x be a child of y (as declared in rbdelete) Only RBT Property 4 might be violated (if y is black) If so, move the violation up tree until we find a place where it can be fixed Total time will be O(log n) // deletion operation if (y->color) == BLACK) rbdeletefixup(t, x); y delete y return y; x x 48
rbdeletefixup(t, x) while (x!= T.root && x->color == BLACK) if (x == x->p->left) // x is a left child w = x->p->right // w is the sibling of x if (w->color == RED) w->color = BLACK; // case 1 x->p->color = RED; // case 1 Case 1 leftrotate(t,x->p); // case 1 w = x->p->right; // case 1 if (w->left->color == BLACK && w->right->color == BLACK) w->color == RED; // case 2 Case 2 x = x->p; // case 2 else if w->right->color == BLACK) w->left->color = BLACK; // case 3 w->color = RED; // case 3 Case 3 rigthrotate(s, x); // case 3 w = x->p->right; // case 3 w->color = x->p->color; // case 4 x->p->color = BLACK; // case 4 w->right->color = BLACK; // case 4 Case 4 leftrotate(t, x->p); // case 4 x->t.root; else // x == x->p->right (same as above, but with right & left exchanged) x->color = BLACK; 49
After a node y is deleted Node y has one child x Move the black to child node x of y move the extra black up tree until a place is found where it can be fixed y delete y stop y delete y x x x x move the extra black up tree 50
if (w->color == RED) w->color = BLACK; x->p->color = RED; leftrotate(t,x->p); w = x->p->right; Case 1: sibling w is red After rotation, the case 1 is converted into cases 2, 3, or 4 x A B D w case 1 B D new w E C E x A C 51
if (w->left->color == BLACK && w->right->color == BLACK) w->color == RED; x = x->p; Case 2,3,4: sibling w is black Case 2 : both children of w are black x A B D w case 2 new x A B D w C E C E 52
53 B A D x w case 2 C E B A D w C E When parent of x is red, as it comes from case 1: Color the sibling w with red Move up the one extra black to the parent Terminate the delete routine
When parent of x is black: Color the sibling w with red Move up the one extra black to the parent Restart the loop from the parent of x. x A B D w case 2 new x A B D w C E C E 54
if (w->left->color == BLACK && w->right->color == BLACK) else if (w->right->color == BLACK) w->left->color == BLACK; w->color = RED; rightrotate(t, w); w = x->p->right; Case 3,4: at least one of children of w is red. Transform case 3 into case 4. x A B C D w E case 3 A B new w C D E 55
w->color = x->p->color; x->p->color = BLACK; w->right->color = BLACK; leftrotate(t, x->p); x = T.root; Case 4: right child of w is red Terminate delete routine at the next loop x A B D w case 4 B D E C E A C 56
Splay Tree Balanced binary search tree Do not have any other information (like color in red-black tree) Restructure tree after each operation (search, insert, delete) so the tree is called Self-reconstructing, self-adjusting, self-organizing tree After search, insert operation Move the node to the root of the tree After delete operation Move the adjacent node to the deleted node to the root Splaying Moves a node to the root by a sequence of rotation 58
Self-reconstructing method (1) By left, right rotation root α x A β C γ α A β C γ 59
Self-reconstructing method (1) By left, right rotation root C C A x α A B β γ δ α A β B δ γ α β B γ C δ 60
Self-reconstructing method (1) Problem: might make the tree unbalanced C D E F C D E A F D E F A B A B B C
Self-reconstructing method (1) Problem: might make the tree unbalanced A E D F A D F E D A E F B C B C B C 62
Self-reconstructing method (2) By zig, zig-zag, zig-zig steps Zig step When parent of node x is the root One left or right rotation root α x A β C γ α A β C γ 63
Zig-zag step When parent of node x is not the root 64 C δ A x α B γ β B A γ δ α β C A C β α δ γ B x x
Zig-zig step When parent of node x is not the root y C A x x α A B β γ δ α β B γ C y δ 65
F F F A E E A F D D D D C A B E B E B B C C A C 66
Splay a node Move it to the root by a sequence of rotation After Search(T, x) If x does not exist Splay the last accessed node If x exist Splay the node x After Insert(T, x) Insert x, and splay the node After Delete(T, x) Delete x, and splay the parent node of the actual node deleted Amortized time complexity O(m log n) where m is the number of operations 67
Finding k-th element Computing the rank
BSTs support Minimum, Maximum, Search, Insertion, Deletion More Query Operations Selection and Rank Selection: k 번째로작은데이터를구하시오. Rank: 주어진데이터가전체데이터에서몇번째인지, 즉순위 (rank) 를계산하시오. With balanced binary search tree (e.g., red-black tree) Query time complexity: O(log n) Insertion and deletion are allowed 69
To handle dynamic order statistic queries Based on red-black tree (or any other BSTs) An additional field size : 주어진노드를루트로하는 subtree 의노드의수 x->size = x->left->size + x->right->size + 1 4 3 7 5 11 1 14 10 15 2 19 4 key size 21 1 2 1 5 1 17 1 70
Selection: find k-th smallest element OSselect(x, k) r = x->left->size + 1; if (r == k) return x; else if (r > k) return OSselect(x->left, k); else return OSselect(x->right, k-r); 14 10 4 3 7 5 11 1 15 2 19 4 key size 21 1 2 1 5 1 17 1 71
Rank: compute the rank of a node x OSrank(T, x) r = x->left->size + 1; y = x; while (y!= T.root) if (y == y->p->right) r += y->p->left->size + 1; y = y->p; return r; 14 10 4 3 7 5 11 1 15 2 19 4 key size 21 1 2 1 5 1 17 1 72
Insertion Size field 값수정 루트노드에서단말노드로내려가면서, 지나가는모든노드의 size 값을 1 증가. 입력데이터를저장하는노드의 size 값을 1 로지정. 각 left, right rotation 마다다음과같이 size 값수정 14 19 y rightrotate(y) 12 19 x 12 11 x 7 leftrotate(x) 6 14 12 y 6 4 4 7 73
Deletion Size field 값수정 노드를 delete 한후, 이노드의부모노드부터시작하여루트노드까지올라가면서지나가는모든노드의 size 값을 1 감소. 각 left, right rotation 마다 insert 연산에서와같이 size 값수정 74
1 차원 Range Query Range Query n 개의실수 S = {a 1, a 2,, a n } 이주어졌을때, 주어진폐구간 (query interval) I=[b 1, b 2 ] 에포함되는 S 의모든원소를찾는문제 Range reporting: report all data Range counting: count the number of data Dynamic operation Insertion, deletion Range tree Supports range queries Range counting: O(log n) Range reporting: O(log n + k) 76
1 차원 Range Tree Balanced binary search tree Properties 단말노드는 n 개의실수 {a 1, a 2,, a n } 를원소로한다. 내부노드는 n-1 개의실수 {a 1, a 2,, a n-1 } 를원소로한다. 77
Example 21 9 35 3 17 27 47 2 7 14 21 47 24 29 58 2 3 7 9 14 17 24 27 29 35 58 64 6 32 78
Query reporting: range [l, r] Step 1: search l, r. 최종적으로도달한단말노드를 t l, t r Step 2: v split 계산 루트노드로부터시작하여단말노드로내려가면서노드 x 의 key 값이 [l, r] 에포함되는첫노드 Step 3: v split 로부터단말노드 t l 로내려가면서 어떤노드 x 의왼쪽 child 로내려갈경우에는이노드 x 의오른쪽 subtree 에속하는모든단말노드의점들은모두주어진 range 에포함되므로이노드들을모두 report 한다. 어떤노드 x 의오른쪽 child 로내려갈경우에는아무런작업을하지않는다. Step 4: v split 로부터단말노드 t r 로내려가면서 (Step 3 의내용과유사함 ) Time complexity : O(log n + k) 79
range [l, r] V split t l t r 80
query reporting: [6,32] 21 9 35 3 17 27 47 2 7 14 21 47 24 29 58 2 3 7 9 14 17 24 27 29 35 58 64 6 32 81
RangeReport1D(T, l, r) // range R = [l, r] vsplit = FindSplitNode(T, l, r); if (vsplit is leaf node) report if vsplit->key is in range R; else v = vsplit->left; while (v is not leaf node) if (l <= v->key) report all leaf nodes of subtree v->right v = v->left; else v = v->right; report if leaf node v->key is in range R; v = vsplit->right; // similarly, symmetrically do the same as above // right & left exchanged FindSplitNode(T, l, r) // range = [l, r] v = T.root; while (v is not a leaf && (r <= v->key or l >= v->key)) if (r <= v->key) v = v->left; else v = v->right; return v; 82
Time complexity : O(log n) - Use field size 21 14 9 7 35 7 3 4 17 3 27 4 47 3 2 7 47 14 24 29 58 2 2 2 21 2 2 2 2 3 7 9 14 17 24 27 29 35 58 64 6 32 83
2 차원 Range Query 2 차원평면상에 n 개의점 P = {p 1, p 2,, p n } 이주어졌을때, 주어진직사각형 R=[a 1, a 2 ][b 1, b 2 ] 영역에포함되는 P 의모든점를계산하는문제 b 2 P R b 1 a 1 a 2 84
2D Range Query Range Query Range reporting: report all data elements Range counting: count the number of data elements 2D Range tree supports 2D range queries Time complexity Range counting: O(log 2 n) Range reporting: O(log 2 n + k) allows dynamic operations Insertion and deletion 85
Construction 1. 먼저 P 에속하는모든점들의 x- 좌표를기준으로 1 차원 range tree T 를만든다. 이트리에서는앞그림에서와같이 x- 좌표가 [a 1, a 2 ] 인수직구간에포함되는모든점에대한 query 가가능 2. 그다음에위에서만든트리 T 의모든내부노드 t 마다, t 를루트로하는 T 의부분트리에속하는모든단말노드에해당하는점들의집합을 Q t 라고하자. Q t 에속하는모든점들에대하여 y- 좌표를기준으로 1 차원 range tree 를만들어이트리 ( 의 root) 를노드 t 에연결한다. 86
Range tree on x-coordinates T Range tree on y-coordinates Q t t Q t 87
88
Range reporting: query range [a, b]x[c, d] 1D range query 를이용 X- 축의좌표로만들어진 range tree 에대하여구간 [a, b] 에대하여 range query 수행 어떤노드 x 에대하여 1 차원 range reporting 하는대신에 노드 x 에연결된 y- 좌표로만들어진 1D range tree 에대하여구간 [c, d] 로다시한번더 1 차원 range reporting 을수행 Time complexity : O(log 2 n + k) 89
x-range tree y-range tree d t a b c Q t Q t 90
RangeReport2D(T, a, b, c, d) // range R = [a, b] [c, d] vsplit = FindSplitNode(T, a, b); if (vsplit is leaf node) report if vsplit->key is in range R; else v = vsplit->left; while (v is not leaf node) if (l <= v->key) RangeReport2D(v->right->Ty, c, d); v = v->left; else v = v->right; report if leaf node v->key is in range R; v = vsplit->right; // similarly, symmetrically do the same as above // right & left exchanged 91
Closed Intervals ( 폐구간 ) [a, b] (a b) [a, b] [c, d] iff (a d) and (c b) [a, b] [c, d] = iff (a > d) or (c > b) a b c d c d a b a c b d 93
Operations IntervalInsert(T, x) : Interval 트리 T 에폐구간을저장하는노드 x 를추가한다. IntervalDelete(T, x) : Interval 트리 T 에서노드 x 를제거한다. IntervalSearch(T, i) : 폐구간 i 와서로겹치는한개 ( 모든 ) 구간을찾는다. Interval Tree Balanced Binary Search Tree 각구간 [low, high] 의 low 값을 key 값으로만든다. Node x x->int : interval stored in node x x->max : 노드 x를루트로하는 subtree 의모든노드에저장된구간의최대값. 94
8 9 0 3 5 6 8 10 26 26 25 30 19 17 20 19 16 15 21 23 [8,9] 23 [16,21] 30 [25,30] 30 interval max [5,8] 10 [15,23] 23 [17,19] 20 [26,26] 26 [0,3] 3 [6,10] 10 [19,20] 20 x->max = MAX(x->int->high, x->left->max, x->right->max) 95
Search: IntervalSearch(T, i) : 폐구간 i 와서로겹치는한개구간을계산한다. IntervalSearch(T, i) x = T.root; while (x!= NULL and i does not overlap x->int) if (x->left!= NULL and x->left->max >= i->low) x = x->left; else x = x->right; return x; Others Q1: Interval tree 에서주어진구간과겹치는모든구간을찾는 IntervalSearchAll() 연산을구현하시오. Q2: Interval tree 에저장된구간과가장많이겹치는임의의점을찾는알고리즘을구현하시오. 96
Operations IntervalInsert(T, x) : Interval 트리 T 에폐구간을저장하는노드 x 를추가한다. IntervalDelete(T, x) : Interval 트리 T 에서노드 x 를제거한다. IntervalSearch(T, i) : 폐구간 i 와서로겹치는모든구간을찾는다. IntervalPointQuery(T, q) : 점 q 를포함하는모든구간을찾는다. IntervalSum(T) : T 에포함된모든 interval 의합집합의길이를계산한다. 97
Interval Tree Fully dynamic structure 어떠한 interval 도 insert, delete 될수있다. 가능한 Operation 이제한적 Segment Tree Semi-dynamic structure interval 이가질수있는끝점의집합 P 가정해짐 끝점이 P 에속하는 interval 만 insert, delete 가능 더많은 Operation 이쉽게구현가능 IntervalPointQuery, IntervalSum 등에유리 98
Construction n 개의폐구간 I = {[a 1, b 1 ], [a 2, b 2 ],, [a n, b n ]} 주어질때, p 1, p 2,, p m 폐구간 I 에속하는구간들의모든끝점을오름차순으로나열 1 차원직선을아래와같은구간으로나눔 기본구간 (elementary interval) 이라고부름 (-, p 1 ), [p 1, p 1 ], (p 1, p 2 ), [p 2, p 2 ], (p 2, p 2 ),, (p m-1, p m ), [p m, p m ], (p m, + ) s 1 s 3 s 2 s 4 s 5 99
Segment Tree Balanced binary search tree 단말노드 매기본구간마다대응하는단말노드를만든다. 모든단말노드는하나의기본구간을갖는다. 내부노드 그노드를 root 로하는모든단말노드에대응하는기본구간의합집합에해당하는 interval 을가진다 즉, 어떤내부노드에대응하는 interval 은그노드의두자식노드에대응하는 interval 의합집합이다. 루트노드에대응하는 interval 은 1 차원전체구간이된다. 각노드 v 에저장하는정보 Int(v): 노드 v 에대응하는 interval I 에속하는 interval 중에서 Int(v) [a, b] 이며 Int(parent(v)) [a, b] 를만족하는모든 interval [a, b] 들을리스트로 v 에저장 100
s 5 s 2, s 5 s 1 s 1 s 1 s 3 s 3, s 4 s 2, s 5 s 3 s 4 s 1 s 3 s 2 s 4 s 5 Space complexity : O(n log n) Time complexity : O(n log n) 101
IntervalPointQuery(T, q) : query point q 를포함하는모든 interval 을찾아서출력 IntervalPointQuerySegmentTree(v, qx) Report all intervals stored at v if (v is not a leaf) if (qx Int(v->left)) QuerySegmentTree(v->left, qx); else QuerySegmentTree(v->right, qx); Time complexity : O(log n + k) k : 출력되는구간의수 102
Insertion InsertSegmentTree(v, a, b) // interval [a,b] if Int(v) [a,b] store [a,b] at v; else if Int(v->left) [a,b] InsertSegmentTree(v->left, a, b); if Int(v->right) [a,b] InsertSegmentTree(v->right, a, b); Deletion Time complexity : O(log n) 103
22 20 15 R 3 R 1 11 7 R 2 4 4 8 12 16 20 28 104
1 차원 Query ( 배열 a[max] 에서 ) Update a[i] Query q i p a [ i] (0 p q MAX ) 2 차원 Query ( 배열 a[max][max] 에서 ) Update a[i][j] Query r 2 ir 1 c 2 jc a[ i][ j] (0 r1 r2 MAX, 0 c1 c2 1 MAX ) 106
Binary Indexed Tree: 1 부터 2 K 까지의자연수를아래와같은계층적그룹으로 나눈구조트리 그룹 (Group) 그룹대표 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 107
Given an input array a[max], Define tree[ ] to store the sum of the group members! tree[ i] a[ k] ks ( i) 22 13 4 2 2 1 1 5 tree[i] 2 1 1 4 0 0 2 0 i a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 1 1 1 0 4 4 0 1 0 1 2 3 0 2 108
tree[ i] k S ( i) a[ k] tree[16] tree[ 16] 16 k1 a[ k] a[16] tree[15] tree[14] tree[12] tree[8] 22 13 4 2 2 1 1 5 tree[i] 2 1 1 4 0 0 2 0 i a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 1 1 1 0 4 4 0 1 0 1 2 3 0 2 109
C[ k] k i1 a[ i] C[13] 13 i1 13 (1101) C[13] tree[(1000) tree[8] tree[12] tree[13] 8 i1 a[ i] 2 a[ i] 12 i9 2 ] tree[(1100) a[ i] 13 i13 a[ i] 2 ] tree[(1101) 22 2 ] 13 4 2 2 1 1 5 tree[i] 2 1 1 4 0 0 2 0 i a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 1 1 1 0 4 4 0 1 0 1 2 3 0 2 110
q i p a[ i] C[ q] C[ p 1] a[ k] C[ k] C[ k 1] 111
a[k] a[k] value 22 13 4 2 2 1 1 5 tree[i] 2 1 1 4 0 0 2 0 i a[i] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 2 0 1 1 1 0 4 4 0 1 0 1 2 3 0 2 112
Operations 어떤멤버의 index 로부터내가속하는모든그룹의그룹대표번호를어떻게구할것인가? 역시 index 연산으로가능 그룹 (Group) 그룹대표 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 113
그룹 (Group) 그룹대표 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 BIT(tree[]) 에서 임의의수 k : 반드시하나의그룹대표 그룹 : S(k) = {k-2 l(k) +1,, k}, (l(k) : k 의 last bit-1 위치 ) k = a1b = a1(00 00) S(k) = { a0(00 01), a0(00 10), a0(00 11),, a0(11 11), a1(00 00) } S(k) = 2 l(k) S(12) = S(1100) = {1001, 1010, 1011, 1100} = {9, 10, 11, 12} 114
Find Last bit-1 of a number N Given N = 1001101101000000 Return 0000000001000000 N & (-N), N & (N ^ (N-1)) Let & : AND, ^ : XOR N = a1b a = (0 1)*, b=0* N : complement of N Then, -N = (a1b) + 1 = a 0b + 1 = a 0(00 0) + 1 = a 0(11 1) + 1 = a 1(00 0) = a 1b N&(-N) = (a1b) & a 1b = (00 0)1(00 0) N&(N^(N-1)) = a1(00 0)&(a1(00 0)^a0(11 1)) = a1(00 0)&((00 0)1(11 1)) = (00 0)1(00 0) 115
Remove Last bit-1 of a number N Given N = 1001101101000000 Return 1001101100000000 N-N & (-N), N- N & (N ^ (N-1)) N&(N-1) Let N = a1b a = (0 1)*, b=0* & : AND, ^ : XOR Then, N&(N-1) = a1(00 0) & (a0(11 1)) = a0(00 0) 116
Cumulative Sum C[ k] k i1 a[ i] int tree[]; int getcumulativesum(int k) { int sum, index; sum = 0; index = k; while (index > 0) { sum += tree[index]; index -= GET_LAST_ONE(index); } return sum; } k = 1001101101000000 index = 1001101101000000 index = 1001101101000000 = 1001101100000000 = 1001101000000000 = 1001100000000000 = 1001000000000000 = 1000000000000000 117
a[k] int tree[]; int size; a[k] value // size of tree void update(int k, int value) { int index; k = 1001101101000000 index = 1001101101000000 } index = k; while (index <= size) { tree[index] += value; index += GET_LAST_ONE(index);//add last significant bit } index = 1001101101000000 = 1001101110000000 = 1001110000000000 = 1010000000000000 = 1100000000000000 = 10000000000000000 118
#define GET_LAST_ONE(N) ((N)^(-(N))) //#define GET_LAST_ONE(k) ((N)&((N)^((N)-1))) void initcumulativesum(int a[], int tree[], int size) { int i, sum, index; } int lastone, removelastone; for(i=1; i<=size; i++) { lastone = GET_LAST_ONE(i); removelastone = i - lastone; sum = a[i]; index = lastone-1; while (index > 0) { sum += tree[removelastone + index]; index -= GET_LAST_ONE(index); } } tree[i] = sum; Time complexity : O(n log n) i = 1001101101000000 lastone = 0000000001000000 removelastone = 1001101100000000 Index = 00000000001111111 Index = 00000000001111111 removelastone + index = 10011011001111111 = 10011011001111110 = 10011011001111100 = 10011011001111000 = 10011011001110000 = 10011011001100000 = 10011011001000000 119
초기화 Step 1: 배열 a[][] 모든행에대하여 1 차원 BIT tree[][] 를만든다 주어진 1 차원배열에대하여그배열자체에 1 차원 BIT 를만들수있음에유의한다. Step 2: 모든행에대하여 1 차원 BIT 가만들어진배열 tree[][] 의모든열에대하여 1 차원 BIT 를만든다. 120
초기화 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 121
초기화이후 tree[][] 의값 1 1 2 3 4 5 6 7 8 1 1 2 3 4 5 6 7 8 2 3 4 5 6 7 8 2 3 4 5 6 7 8 122
Cumulative Sum C(p, q) p q i1j1 a[i][j] int tree[][]; int getcumsum2d(int p, int q) { int sum, index; sum = 0; for(i=p; i>0; i-=get_last_one(i)) for(j=q; j>0; j-=get_last_one(j)) sum += tree[i][j]; } return sum; } Query (Partial Cumulative Sum) p2 q 2 i p1j q 1 a[i][j] C(p,q ) C(p,q ) C(p 1,q ) C(p 1,q 2 2 2 1 1 1 2 1 1 1) 123
Update a[p][q] a[p][q] value int tree[][]; int size_x, size_y; // size of tree void update(int p, int q, int value) { int ix, iy; ix = p; } while (ix <= size_x) { iy = q; while (iy <= size_y) { tree[ix][iy] += value; iy += GET_LAST_ONE(iY); } ix += GET_LAST_ONE(iX); } 124
초기화 #define GET_LAST_ONE(N) ((N)^(-(N))) //#define GET_LAST_ONE(k) ((N)&((N)^((N)-1))) void initcumsum2d(int a[][max], int tree[][max], int size) { int i, j, sum, index; int lastone, removelastone; for(i=1; i<=size; i++) { for(j=1; j<=size; j++) { lastone = GET_LAST_ONE (j); removelastone = j - lastone; sum = a[i][j]; index = lastone - 1; while(index > 0) { sum += a[i][removelastone + index]; index -= GET_LAST_ONE (index); } tree[i][j] = sum; } for(j=1; j<=size; j++) { lastone = GET_LAST_ONE (i); removelastone = i - lastone; sum = tree[i][j]; index = lastone - 1; while(index > 0) { sum += tree[removelastone + index][j]; index -= GET_LAST_ONE (index); } tree[i][j] = sum; } } } 125
http://community.topcoder.com/tc?module= Static&d1=tutorials&d2=binaryIndexedTrees