CSCA48H3 Lecture Notes - Lecture 17: Self-Balancing Binary Search Tree, Avl Tree, Hash Table
17 Apr 2018
School
Department
Course
Professor
Document Summary
A search operation is as important as insertion and removal operations in most data structures. Time complexity, o(n), is not satisfactory if n is large. List-based binary search (remember you should have a sorted list) Will be covered in more detail in cscb63. Need a proper hash table (an array of size n & a hash function) Avl tree is a bst, such that for each node in the tree, the height of its right and left children differs at most by 1. Assume that we only store data in internal nodes and all external nodes contain none. The height of an avl tree is log(n) Search() and find() running time is o(log(n)) Trinode restructuring transforms the tree into a balanced tree. Go up the tree from the newly added node (or parent of the deleted node) to find the first node that does not maintain avl property. Rename xyz to abc such that in-order traversal generates abc .
