COIS 2020H Lecture 5: Binary Search Tree

• School: Trent University
• Department: Computing & Information Systems
• Course: COIS 2020H
• Professor: Brian G.Patrick

Document Summary

Quiz 5 on thursday, july 28 covers binary search trees (insertions and deletions) and avl trees (insertions only). Quiz 5 is composed of true/false questions (8 marks) and three demonstration questions (17 marks) for a total of 25 marks. 3 methods: add (t item, remove (t item, bool contains (t item) true/fuls. Infix: 11, 33, 34, 35, 44, 55, 68, 70. Remove (t item: no children, one child, two children. Ex: when we remove the 44: snip it off. Ex: when we remove the 35 & 68: go around and connect with the child. Ex: when we remove the 33: replace the item with either: a. i. 1. a. i. 2. Then delete the node from where is coming from & choose from (a or b) In the worst case, the depth of bst in a node was -1. Preferably, was a depth of [log2 ] <<< (balanced) Avl tree guarantee a worst case depth of [log2 ]