CS136 Study Guide - Binary Search Tree, Avl Tree
Document Summary
A binary search tree with an extra balancing condition. (recall in a binary search tree every node"s key is larger than its left child"s key and smaller than its right child"s key. ) Balancing condition: for every node, the height of the trees formed by the node"s children di er by at most 1. Insert/delete: like in a normal bst, but perform a clean-up" procedure afterward, which consists of a number of rotations. 1 right left rotation x z x y z y z x y (right rotation on {y, z} and then left rotation on {x, z}) Example: insert the following keys into an avl tree: 11, 8, 10, 5, 6, 4, 13, 15, 14 (in that order). insert 11 insert 8. A generalization of a binary search tree where the nodes can contain up to two keys and three children.
