Average depth of randomly generated binary search trees

Average depth of randomly generated binary search trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
Comment
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 © 2006-2013 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 A-J 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.889