Weight balanced tree ppt

balanced trees in data structure ppt and amortized weight balanced trees ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
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 ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 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 dwharderalumni.uwaterloo.ca

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.