CSC 226 Lecture Notes - Lecture 8: Binary Search Tree, Avl Tree, Binary Search Algorithm
27 Sep 2016
School
Department
Course
Professor
Document Summary
Proof: assume that inserting k into t results in a new unbalanced tree t" with at least one unbalanced node. Let z be the unbalanced node when walking up from node w that contains key k. The height of the subtree s rooted at node z before insertion the same height of the subtree s* rooted at after rebalancing. Height of s = height of s*, therefore height of t = height of t*. Label nodes that need restructuring bottom to top as x,y,z and left to right as a,b,c. Nodes can hold more than one key. 0 nodes: hold no keys and have no children: all at the same depth. 2 nodes: holds one key has two children. 3 nodes: holds two keys and has three children. As a search tree, it is sorted similarly to binary search trees. 2 nodes are treated the same way as nodes from binary search trees.
