CSE 100 Study Guide - Quiz Guide: Avl Tree, Hash Table, Double Hashing

• School: UCSD
• Department: Computer Science & Engineering
• Course: CSE 100
• Professor: Nuno Bandeira

Document Summary

Question: what is the worst case time to find a single element in hash table with. Second hash function in double hashing is the offset, i. e how much space to. N elements in it? (linear probing) o(n) jump. Self-balancing tree that achieves a worst case time complexity of o(logn) For all nodes in the tree, the heights of the two child subtrees of the node differ by at most one. The balance factor of a node u is equal to the height of u"s right subtree minus the height of u"s left subtree. A bst is an avl if for all nodes u in the tree, the balance factor of u is either -1, 0, 1. Perform regular bst insertion algorithm, then starting at the newly-inserted node, traverse up the tree and update the balance factor of each of the new node"s ancestor. For any node that is out of balance, perform avl rotations to fix balance.