Question? Leave a message!

Balanced Trees

Balanced Trees
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 © 20062013 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 subtreeBalanced 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 – Nullpathlength balancing: comparing the nullpathlength of each of the two subtrees (the length to the closest null subtree/empty node) – Weight balancing: comparing the number of null subtrees 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 RedBlack Trees Redblack 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 RedBlack Trees Redblack trees are nullpathlength balanced in that the nullpath length going through one subtree must not be greater than twice the nullpath length going through the other – A perfect tree of height h has a nullpath length of h + 1 – Any other tree of height h must have a nullpathlength less than h + 1Balanced trees 12 WeightBalanced 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 WeightBalanced Trees The ratios of the empty nodes at the root node are 5/10 and 5/10Balanced trees 14 WeightBalanced Trees The ratios of the empty nodes at this node are 2/5 and 3/5Balanced trees 15 WeightBalanced Trees The ratios of the empty nodes at this node, however, are 4/5 and 1/5Balanced trees 16 WeightBalanced 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 WeightBalanced 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 – Redblack trees use nullpathlength 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.193212, 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
Document Information
User Name:
User Type:
United Kingdom
Uploaded Date: