Question? Leave a message!




Average depth of randomly generated binary search trees

Average depth of randomly generated binary search trees
ECE 250 Algorithms and Data Structures Average depth of randomly generated binary search trees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 20062013 by Douglas Wilhelm Harder. Some rights reserved.Average depth of randomly generated binary search trees 2 Outline In this topic, we will: – Determine the average depth of a node in a randomly generated binary search tree – We will introduce a few examplesAverage depth of randomly generated binary search trees 3 Average Depth of a Node To proceed, we will determine what is the average height of a randomly generated binary search tree The total internal path length is the sum of the depths of all the nodes with a tree – The average depth is the total internal path length over the number of nodes: 34  2.6 13Average depth of randomly generated binary search trees 4 Average Depth of a Node Consider the ten letters AJ inserted in these two orders:Average depth of randomly generated binary search trees 5 Average Depth of a Node Next, insert C and H, respectively...Average depth of randomly generated binary search trees 6 Average Depth of a Node H and G...Average depth of randomly generated binary search trees 7 Average Depth of a Node A and D...Average depth of randomly generated binary search trees 8 Average Depth of a Node E and E...Average depth of randomly generated binary search trees 9 Average Depth of a Node J and A...Average depth of randomly generated binary search trees 10 Average Depth of a Node G and J...Average depth of randomly generated binary search trees 11 Average Depth of a Node B and C...Average depth of randomly generated binary search trees 12 Average Depth of a Node I and F...Average depth of randomly generated binary search trees 13 Average Depth of a Node and finally D and IAverage depth of randomly generated binary search trees 14 Average Depth of a Node The total internal path lengths 19 25Average depth of randomly generated binary search trees 15 Average Depth of a Node The average depths 1.9 2.5Average depth of randomly generated binary search trees 16 Average Depth of a Node Best and worst average depths: 1.9 4.5Average depth of randomly generated binary search trees 17 Average Depth of a Node Now for the more general question: – What is the average depth of a node in a binary search tree We will calculate the average total internal path length in a binary search tree – we will represent this by I(n) The average depth will be I(n)/nAverage depth of randomly generated binary search trees 18 Average Depth of a Node To begin, I(1) = 0 and I(2) = 1 Therefore the average depths for trees with 1 and 2 nodes are 0 and 0.5, respectivelyAverage depth of randomly generated binary search trees 19 Average Depth of a Node What is I(3) The three nodes values 1, 2, 3 could be added into a binary search tree in one of 3 different ways: 1,2,3 1,3,2 2,1,3 2,3,1 3,1,2 3,2,1Average depth of randomly generated binary search trees 20 Average Depth of a Node Counting the total internal path lengths: 3 + 3 + 2 + 2 + 3 + 3 = 16 The average total internal path length is 16 I(3) 2.67 6 The average depth is I(3)/3 ≈ 0.889Average depth of randomly generated binary search trees 21 Average Depth of a Node Finally, consider all binary search trees with four nodes: • Thus and I(4)/4 ≈ 1.21 116 I(4) 2.67 24Average depth of randomly generated binary search trees 22 Average Depth of a Node Notice that half the trees are optimal:Average depth of randomly generated binary search trees 23 Average Depth of a Node We also have a symmetry that we can exploitAverage depth of randomly generated binary search trees 24 Average Depth of a Node We, however, need a more general formula Suppose we are randomly generating trees from the ten letters A, B, ..., J Each could appear with equal likelihood (1/10) as the rootAverage depth of randomly generated binary search trees 25 Average Depth of a Node Lets look at two of these cases: The average total path length is: – The sum of the two average total path lengths of the two sub trees – Plus one for each node, as each path length to each of the 9 nodes is increased by 1Average depth of randomly generated binary search trees 26 Average Depth of a Node Consequently, we have the following formula: I(0) I(n1) I(1) I(n 2) I(n 2) I(1) I(n1) I(0)  n1 1 I(n) I(i) I(ni1)n1   n i0 n1 2 ni1 I( )  n i0 Multiplying both sides by n yields n1 n I(n)n(n1) 2 I(i)  i0Average depth of randomly generated binary search trees 27 Average Depth of a Node To get rid of the sum, write the equation both for I(n) and I(n – 1) and subtract n1 n I(n)n(n1) 2 I(i)  i0 Substitute n with n – 1 n2  (n1)I(n1) (n1)(n 2) 2 I(i)    i0 nI(n)(n1)I(n1) 2n 2 2I(n1)Average depth of randomly generated binary search trees 28 Average Depth of a Node This gives us a recurrence relation which we may solve in Maple: rsolve( nIn(n) (n 1)In(n 1) = 2n 2 + 2In(n 1), In(1) = 0, In(n) ); 2 2n 2 n 4n 2   n asympt( , n ); 1  2 ln n 2 n 2ln n1 2O    n Average depth of randomly generated binary search trees 29 Average Depth of a Node This gives us the approximation I(n) ≈ 2 (ln(n) +  – 2)n and thus the average depth of a node is I(n)  2 ln(nn ) 2(ln( ))  nAverage depth of randomly generated binary search trees 30 Average Depth of a Node The course web site has a Randomtree class that can be used to generate such search trees – These points are the averages of 1000 pseudorandomly generated N trees with heights n = 2 nodes for N = 0, …, 15 2 ln(n) 2  nAverage depth of randomly generated binary search trees 31 Average Height of a Node Incidentally, the average height of 1000 pseudorandomly generated trees also grows logarithmically – Approximately twice the average depth – Recall that the average depth of a perfect binary tree is h – 1 2ln(n) 6.5 nAverage depth of randomly generated binary search trees 32 Average Depth of a Node The consequence of this is reassuring: – The average depth of a node in a randomly generated tree has depth (ln(n)) and the average height also appears to be (ln(n)) Unfortunately, this is only the average: the worst case is still (n)Average depth of randomly generated binary search trees 33 Summary This topic covered the average depth of a randomly generated tree – Taking n linearly ordered objects and placing them into a tree will produce a tree with an average depth of (ln(n)) – The average height also appears to grow logarithmically – There may be nodes that are at deeper average depths, but there are an insufficient number of these (again, on average) to affect the average run timesAverage depth of randomly generated binary search trees 34 Usage Notes • These slides are made publicly available on the web for anyone to use • If you choose to use them, or a part thereof, for a course at another institution, I ask only three things: – that you inform me that you are using the slides, – that you acknowledge my work, and – that you alert me of any mistakes which I made or changes which you make, and allow me the option of incorporating such changes (with an acknowledgment) in my set of slides Sincerely, Douglas Wilhelm Harder, MMath dwharderalumni.uwaterloo.ca
Website URL
Comment