COMPSCI 61B Lecture Notes - Lecture 22: Self-Balancing Binary Search Tree, Binary Logarithm, Binary Tree

• School: Berkeley
• Department: Computer Science
• Course: COMPSCI 61B
• Professor: Joshua Hug

Document Summary

Problem: leaves can get too stu ed, and we run into the same problem as before. Node splitting: bump up the second element and pull out the rst value out of an overstu ed node, making it its own node. Node splitting can cause you to create a new root. If we split the root, every node gets pushed down by exactly one level. If we split a leaf node or internal node, the height doesn"t change. M: max number of children (means that there are max m-1 elements in a leaf) Max number of splitting operations per insert: ~height of tree. B-tree of order m = 4 is a 2-3-4 tree. B-tree of order m = 3 is a 2-3 tree. Small m (3, 4): conceptually simple balanced search tree. M is large (thousands): used for databases and lesystems. Goal: rotate a tree about a given node left or right.