Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7AVL Trees4-27-2011Opening DiscussionDo you have any questions about the quiz?Minute essay comments:Relationship of a “script” with programming. Not directly related to actors.Balanced BSTsThe critical flaw of BSTs is that they can become unbalanced leading to O(n) behavior instead of O(n log n).There are approaches to keeping trees balanced where you alter the structure of the tree occasionally.It has to be O(log n) or else it isn't worth it.AVL TreesOne approach to maintaining balance is the AVL tree.Each node should keep track of its height. The height of the left and right children should not differ by more than one. If it does, a modification is made to bring it back into balance.This can be done by running back up through the nodes to the root on an add or remove and doing rotations when things aren't balanced.RotationsDepending on the structure in the imbalance, you do either a single or double rotation. Tall outer grandchild is single, tall inner grandchild is double.Image from Wikimedia Commons, AVL tree entry.Functional TreesYou can do AVL trees in a non-functional way by keeping track of parents so you can walk back up.You can also do them functionally with immutable nodes by rebuilding altered nodes and the path back to the root.Minute EssayAny final requests before the last
View Full Document
Unlocking...