Question? Leave a message!




Complete binary trees

Complete binary trees
ECE 250 Algorithms and Data Structures Complete binary Douglas Wilhelm Harder, M.Math. LEL trees 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.Complete binary trees 2 Outline Introducing complete binary trees – Background – Definitions – Examples – Logarithmic height – Array storageComplete binary trees 3 5.3 Background A perfect binary tree has ideal properties but restricted in the h number of nodes: n = 2 – 1 1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, .... We require binary trees which are – Similar to perfect binary trees, but – Defined for all nComplete binary trees 4 5.3.1 Definition A complete binary tree filled at each depth from left to right:Complete binary trees 5 5.3.1 Definition The order is identical to that of a breadthfirst traversalComplete binary trees 6 5.3.1 Recursive Definition Recursive definition: a binary tree with a single node is a complete binary tree of height h = 0 and a complete binary tree of height h is a tree where either: – The left subtree is a complete tree of height h – 1 and the right sub tree is a perfect tree of height h – 2, or – The left subtree is perfect tree with height h – 1 and the right subtree is complete tree with height h – 1Complete binary trees 7 5.3.2 Height Theorem The height of a complete binary tree with n nodes is h = ⌊lg(n)⌋ Proof: – Base case: • When n = 1 then ⌊lg(1)⌋ = 0 and a tree with one node is a complete tree with height h = 0 – Inductive step: • Assume that a complete tree with n nodes has height ⌊lg(n)⌋ • Must show that ⌊lg(n + 1)⌋ gives the height of a complete tree with n + 1 nodes • Two cases: – If the tree with n nodes is perfect, and – If the tree with n nodes is complete but not perfectComplete binary trees 8 5.3.2 Height Case 1 (the tree is perfect): – If it is a perfect tree then • Adding one more node must increase the height h + 1 – Before the insertion, it had n = 2 – 1 nodes: h h 11 h 2 21 2 h h 11 h hh lg 2 lg 21 lg 21  h1  hh lg 211    lgnh – Thus,   hh  11   lgnh1 lg 211 lg 21 – However,    Complete binary trees 9 5.3.2 Height Case 2 (the tree is complete but not perfect): – If it is not a perfect tree then hh1 2 n 21 hh1 21 n1 2 hh1 h lg 21 lg n1 lg 2 h1   h  h lg 21 lg n1 h1     – Consequently, the height is unchanged: ⌊lg( n + 1 )⌋ = h By mathematical induction, the statement must be true for all n ≥ 1Complete binary trees 10 5.3.3 Array storage We are able to store a complete tree as an array – Traverse the tree in breadthfirst order, placing the entries into the arrayComplete binary trees 11 5.3.3 Array storage We can store this in an array after a quick traversal:Complete binary trees 12 5.3.3 Array storage To insert another node while maintaining the completebinarytree structure, we must insert into the next array locationComplete binary trees 13 5.3.3 Array storage To remove a node while keeping the completetree structure, we must remove the last element in the arrayComplete binary trees 14 5.3.3 Array storage Leaving the first entry blank yields a bonus: – The children of the node with index k are in 2k and 2k + 1 – The parent of node with index k is in k ÷ 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Complete binary trees 15 5.3.3 Array storage Leaving the first entry blank yields a bonus: – In C++, this simplifies the calculations: parent = k 1; leftchild = k 1; rightchild = leftchild 1; 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Complete binary trees 16 5.3.3 Array storage For example, node 10 has index 5: – Its children 13 and 23 have indices 10 and 11, respectively 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Complete binary trees 17 5.3.3 Array storage For example, node 10 has index 5: – Its children 13 and 23 have indices 10 and 11, respectively – Its parent is node 9 with index 5/2 = 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17Complete binary trees 18 5.3.4 Array storage Question: why not store any tree as an array using breadthfirst traversals – There is a significant potential for a lot of wasted memory Consider this tree with 12 nodes would require an array of size 32 – Adding a child to node K doubles the required memory Complete binary trees 19 5.3.4 Array storage In the worst case, an exponential amount of memory is required These nodes would be stored in entries 1, 3, 6, 13, 26, 52, 105Complete binary trees 20 Summary In this topic, we have covered the concept of a complete binary tree: – A useful relaxation of the concept of a perfect binary tree – It has a compact array representationComplete binary trees 21 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
sharer
Presentations
Free
Document Information
Category:
Presentations
User Name:
Dr.SethPatton
User Type:
Teacher
Country:
United Kingdom
Uploaded Date:
22-07-2017