Question? Leave a message!

AVL Trees

AVL Trees
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures AVL 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.AVL trees 2 Outline Background Define height balancing Maintaining balance within a tree – AVL trees – Difference of heights – Maintaining balance after insertions and erases – Can we store AVL trees as arrays?AVL trees 3 Background From previous lectures: – Binary search trees store linearly ordered data – Best case height:Q(ln(n)) – Worst case height: O(n) Requirement: – Define and maintain a balance to ensure Q(ln(n)) height AVL trees 4 Prototypical Examples These two examples demonstrate how we can correct for imbalances: starting with this tree, add 1:AVL trees 5 Prototypical Examples This is more like a linked list; however, we can fix this…AVL trees 6 Prototypical Examples Promote 2 to the root, demote 3 to be 2’s right child, and 1 remains the left child of 2AVL trees 7 Prototypical Examples The result is a perfect, though trivial treeAVL trees 8 Prototypical Examples Alternatively, given this tree, insert 2 AVL trees 9 Prototypical Examples Again, the product is a linked list; however, we can fix this, tooAVL trees 10 Prototypical Examples Promote 2 to the root, and assign 1 and 3 to be its childrenAVL trees 11 Prototypical Examples The result is, again, a perfect tree These examples may seem trivial, but they are the basis for the corrections in the next data structure we will see: AVL treesAVL trees 12 AVL Trees We will focus on the first strategy: AVL trees – Named after Adelson-Velskii and Landis Balance is defined by comparing the height of the two sub-trees Recall: – An empty tree has height –1 – A tree with a single node has height 0AVL trees 13 AVL Trees A binary search tree is said to be AVL balanced if: – The difference in the heights between the left and right sub-trees is at most 1, and – Both sub-trees are themselves AVL treesAVL trees 14 AVL Trees AVL trees with 1, 2, 3, and 4 nodes:AVL trees 15 AVL Trees Here is a larger AVL tree (42 nodes):AVL trees 16 AVL Trees The root node is AVL-balanced: – Both sub-trees are of height 4:AVL trees 17 AVL Trees All other nodes (e.g., AF and BL) are AVL balanced – The sub-trees differ in height by at most oneAVL trees 18 Height of an AVL Tree By the definition of complete trees, any complete binary search tree is an AVL tree Thus an upper bound on the number of nodes in an AVL tree of h + 1 height h a perfect binary tree with 2 – 1 nodes – What is an lower bound?AVL trees 19 Height of an AVL Tree Let F(h) be the fewest number of nodes in a tree of height h From a previous slide: F(0) = 1 F(1) = 2 F(2) = 4 Can we find F(h)?AVL trees 20 Height of an AVL Tree The worst-case AVL tree of height h would have: – A worst-case AVL tree of height h – 1 on one side, – A worst-case AVL tree of height h – 2 on the other, and – The root node We get: F(h) = F(h – 1) + 1 + F(h – 2)