CST370 - Week 6
CST370 Week 6 This week, we learned more about tree balancing and hashing. AVL trees are self-balancing binary search trees where the balancing factor of each node is either 1 (left), 0, or -1 (right). The balancing factor is calculated by how many 'edges' traveled from the node to the last leaf it can reach (or the height of the subtree): Balancing factor = height of left subtree - height of right subtree To maintain AVL trees, rotations may need to be made on nodes. For left-heavy trees (or subtrees), R-rotations are typically used, while right-heavy trees (or subtrees) use L-rotations. Rotations can be used multiple times in a row, like two R-rotations needed. 2-3 trees are binary search trees that must have at least 2 or 3 children to each node. Each node can contain one value or two values - if it has one value, it will have 2 children, and if it has two values, it will have 3 children. The children can contain one or two ...