CMPSC 130A Study Guide - Final Guide: Dspace, Prims, Adjacency Matrix
Document Summary
Definition: a type of bst with a balance/height constraint, balance/height constraint: every node in the avl tree has a height imbalance of at most 1. Avl trees: |height(left subtree) height(right subtree)| 1, ensures that the depth of the tree is (log ) Insertion occurs on the outside : left-left or right-right. Fixed by a single rotation of the tree: cases 2 and 3 are mirror image symmetries with respect to. Insertion occurs on the inside : left-right or right-left. If the height of 01 does not change, you are done. Avlnode(const comparable & ele, avlnode *lt, avlnode *rt, int h = 0) Avlnode(comparable && ele, avlnode *lt, avlnode *rt, int h = 0) * return the height of a node t or -1 if nullptr int height(avlnode *t) const { * internal method to insert into a subtree. // assume t is balanced or within one of being balanced void balance(avlnode * & t) {
