CSC263H5 Lecture Notes - Lecture 4: Avl Tree
15 Mar 2018
School
Department
Course
Professor
Document Summary
Csc209h5s - software programming and tools (winter 2018) Week 4 - balanced tree (january 26, 2018) Recap: data structures for implementing the dictionary adt. Balanced search trees and balanced bst can be implemented in o(h); h being the height of the tree. Invented by georgy a delson- v elsky and e. m. L h (x) h (x) height of x"s right subtree height of x"s left subtree. Balance factor - an extra attribute to each node in a bst hr (x) hl (x) Bf(x) > 1 or < -1: x is imbalanced. When measuring the height of special trees, you measure it by the number of edges. A tree with a starting node and a left and right child has a height of 1. A tree with only 1 node at the top level has a height of 0. Nil (no tree) has the height of -1.
