Question? Leave a message!

Balanced Trees

Balanced Trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Balanced Trees Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Balanced trees 2 Outline In this topic, we will: – Introduce the idea of balance – We will introduce a few examplesBalanced trees 3 Background Run times depend on the height of the trees As was noted in the previous section: – The best case height is Q(ln(n)) – The worst case height is Q(n) The average height of a randomly generated binary search tree is actually Q(ln(n)) – However, following random insertions and erases, the average height  tends to increase to Q nBalanced trees 4 4.9.1 Requirement for Balance We want to ensure that the run times never fall into w(ln(n)) Requirement: – We must maintain a height which is Q(ln(n)) To do this, we will define an idea of balanceBalanced trees 5 4.9.1 Examples For a perfect tree, all nodes have the same number of descendants on each side Perfect binary trees are balanced while linked lists are notBalanced trees 6 4.9.1 Examples This binary tree would also probably not be considered to be “balanced” at the root nodeBalanced trees 7 4.9.1 Examples How about this example? – The root seems balanced, but what about the left sub-tree?Balanced trees 8 4.9.1 Definition for Balance We must develop a quantitative definition of balance which can be applied Balanced may be defined by: – Height balancing: comparing the heights of the two sub trees – Null-path-length balancing: comparing the null-path-length of each of the two sub-trees (the length to the closest null sub-tree/empty node) – Weight balancing: comparing the number of null sub-trees in each of the two sub trees We will have to mathematically prove that if a tree satisfies the definition of balance, its height is Q(ln(n))Balanced trees 9 4.9.2 Definition for Balance We will see one definition of height balancing: – AVL trees We will also look at B+-trees – Balanced trees, but not binary treesBalanced trees 10 Red-Black Trees Red-black trees maintain balance by – All nodes are colored red or black (0 or 1) Requirements: – The root must be black – All children of a red node must be black – Any path from the root to an empty node must have the same number of black nodesBalanced trees 11 Red-Black Trees Red-black trees are null-path-length balanced in that the null-path length going through one sub-tree must not be greater than twice the null-path length going through the other – A perfect tree of height h has a null-path length of h + 1 – Any other tree of height h must have a null-path-length less than h + 1Balanced trees 12 Weight-Balanced Trees Recall: an empty node/null subtree is any position within a binary tree that could be filled with the next insertion: – This tree has 9 nodes and 10 empty nodes:Balanced trees 13 Weight-Balanced Trees The ratios of the empty nodes at the root node are 5/10 and 5/10Balanced trees 14 Weight-Balanced Trees The ratios of the empty nodes at this node are 2/5 and 3/5Balanced trees 15 Weight-Balanced Trees The ratios of the empty nodes at this node, however, are 4/5 and 1/5Balanced trees 16 Weight-Balanced Trees BB(a) trees (0 a ≤ 1/3) maintain weight balance requiring that neither side has less than a a proportion of the empty nodes, i.e., both proportions fall in a, 1 –a – With one node, both are 0.5 – With two, the proportions are 1/3 and 2/3 Balanced trees 17 Weight-Balanced Trees If a is bounded by 12 0.25a1 0.2929 42 then it will be possible to perform all operations in Q(ln(n)) time – If a is smaller than 0.25 (larger range) the height of the tree may be w(ln(n)) 2 1 – If a is greater than , the operations required to maintain balance 2 may be w(ln(n))Balanced trees 18 Summary In this talk, we introduced the idea of balance – We require O(ln(n)) run times – Balance will ensure the height is Q(ln(n)) There are numerous definitions: – AVL trees use height balancing – Red-black trees use null-path-length balancing – BB(a) trees use weight balancingBalanced trees 19 References Blieberger, J., Discrete Loops and Worst Case Performance, Computer Languages, Vol. 20, No. 3, pp.193-212, 1994. Balanced trees 20 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