COMPSCI 61B Lecture Notes - Lecture 18: Binary Search Algorithm
Document Summary
2-3 and 2-3-4 trees are a real pain to implement, and suffer from performance problems. Interconversion of nodes between 2 nodes and 3 nodes. Walking up the tree to split nodes. Suppose we have a bst with the numbers 1, 2, 3. The specific bst you get is based on the insertion order. More generally, for n items, there are catalan(n) different bsts. Given any bst, it is possible to move to a different configuration using rotation . Tree rotation rotateleft(g): let x be the right child of g. make g the new left child of x. Can think of as temporarily merging g and p, then sending g down and left. Not that for this example, this increased the height of tree rotateright(p): let x be the left child of p. make p the new right child of x. Can think of as temporarily merging g and p, then sending p down and right.
