Balanced Trees 1 Motivation Example Reporting (2-D) Given a set of points S on the plane, preprocess them to build structure that allows efficient queries of the from: Given an rectangle R=[x1,x2][y1,y2] find all points in S that are in the rectangle. P3 P8 P5 P2 P6 P4 P1
P7 2 Summary Add Delete Find Arrays Linked List Bal. Trees Simple, fast Inflexible O(1) O(n) inc sort O(n) Simple
Flexible O(1) O(n) - inc sort O(1) - any O(n) - specific O(n) (no binary search) Not-So-simple Flexible O(logn) O(n) O(logn) binary search O(log n) O(log n) 3 Order statistics Trees
rank and select 4 The dictionary ADT Insert(x,D) Delete(x,D) Find(x,D): Returns a pointer to x if x D, and a pointer to the successor or predecessor of x if x is not in D 5 Suppose we want to add to the dictionary ADT Select(i,D): Returns the ith element in the dictionary: An element x such that i-1 elements are smaller than x 6
Select(5,D) 89 19 20 26 90 21 34 4 67 73 70
77 7 Can we still use trees ? 4 19 20 21 26 34 67 70
73 77 89 90 8 For each node v store # of leaves in the subtree of v 12 4 8 2 4 19
2 20 4 4 2 2 21 26 34 67 70 2
2 73 77 89 90 9 Select(7,T) 12 4 8 2 4 19
2 20 4 4 2 2 21 26 34 67 70 2
2 73 77 89 90 10 Select(7,T) 12 Select(3, ) 4 8 2 4
19 2 20 4 4 2 2 21 26 34 67 70
2 2 73 77 89 90 11 Select(7,T) 12 4 Select(3, ) 2 4
19 8 2 20 4 4 2 2 21 26 34 67
70 2 2 73 77 89 90 12 Select(7,T) 12 4 8
2 4 19 2 20 4 4 Select(1,) 2 2 21 26 34 67
70 2 2 73 77 89 O(logn) worst case time, in case of balanced tree 90 13 Rank(x,T) Return the index of x in T 14
Rank(x,T) Need to return 9 x 15 12 4 8 2 4 19 2 20 4
4 2 2 21 26 34 67 70 2 2 73 77
x Sum up the sizes of the subtrees to the left of the path 89 90 16 Insert (non-balanced tree) 12 8 4 2 17 Insert (cont) 13 9
5 3 2 update only O(h) sizes 18 Summary Insertion and deletion and other dictionary operations still take O(log n) time for balanced trees 19 Orthogonal range searching Range trees 20 Reporting (1-D)
Given a set of points S on the line, preprocess them to build structure that allows efficient queries of the from: Given an interval I=[x1,x2] find all points in S that are in the interval. 6 2 4 5 17 7 8 12 15 19 21 Reporting (1-D)
Build a balanced tree over the points Concatenate them in a list 6 2 4 5 17 7 8 12 15 19 query: O(log n+k) space: O(n) 7
4 12 2 2 5 4 5 8 7 8 15
12 15 22 19 Counting (1-D) Given a set of points S on the line, preprocess them to build structure that allows efficient queries of the from: Given an interval I=[x1,x2] return the # of points in the interval 6 2 4 5 17 7 8 12
15 19 23 Counting (1-D) Build a balanced tree over the points, with subtree sizes. Return: Rank(x2,T)- Rank(x1,T)+1 6 2 4 5 17 7 8 12 15
19 query: O(log n) space: O(n) 7 4 12 2 5 8 2 1 2
4 5 7 15 1 8 12 15 24 19 Reporting (2-D) Given a set of points S on the plane, preprocess them to build structure that allows efficient
queries of the from: Given an rectangle R=[x1,x2][y1,y2] find all points in S that are in the rectangle. P3 P8 P5 P2 P6 P4 P1 P7 25 Range Trees (2-D) Maintain the points in a balanced search tree ordered by x-coor. In each internal node maintain the points in its subtree in a balanced search tree ordered by y
P3 P3 P2 P2 P4 P4 P1 P1 P1 P2 P3 26 P4
Range Trees (Contd.) P3 P8 P5 P2 P6 P4 P7 P1 P3 P2 P4 P1 P1 P2
P3 P4 P5 P6 P7 P8 27 Range Trees (Contd.) P3 P8 P5 P2
P6 P4 P7 P1 P3 P2 P4 P1 P1 P2 P3 P4 P5 P6
P7 P8 28 Query processing Search by the first dimension gives us O(logn) trees which together contain the output. We search each of these trees to get the answer 29 Analysis (2-D) Space O(nlog n) Query O(log2 n+k) 30 Further facts
Generalizes to d-dimensions 31 1 , pi (.)xi,yi insert(x,y), ) delete(x,y), find(x,y ) ,O(log n ),CountPointsAtDistance(d1,d2 : d1,d2 d1 d2 ( ( )x,y ). )CountPointsAtDistance(d1,d2 . 32 1 .d ( )x,y
. ORDER STAT . 33 .d2- .a : .d1- .b : .a-b+1 " .O(log n) W.C . 34 2 insert(x),
) , ,delete(x), find(x ,x )(multiple_of_5 x, y ,y=5x ( .)false WC . 35 2 . .5 . , . ( , ). )(Multiple_of_5 . 36 3
S n , W.C. O(n), find , : W.C find ) ,O(n n/log n , find ). O(log n , insert .delete 37 3 n/log n . ) .O(n . find . ) .O(log n ).O(n 38 4
39 ( )n,m : n,,1,2,3, .1 m . , . ' , . , '. ( 4) : ( )7,3 ( 4,7,3,1,6,2,5 !) ,n (.)n,n/2 :4 )O(nlogn
40 4 - 41 1 n ." ( )1+ .size .1 ,I ( mod k )I+n/2 OS_Select k ( size ). , . 1 2 - .