SYSC 2003 Lecture Notes - Lecture 16: Binary Search Tree, Search Algorithm

• School: Carleton University
• Department: Systems and Computer Engineering
• Course: SYSC 2003
• Professor: bobbychawla

Document Summary

Use search algorithm to locate the item with the specified key. If the item is found, remove the item from the tree. If n is a leaf: set the reference in n"s parent to null. If n has only one child: let n"s parent adopt n"s child. If n has two children: locate another node m that is easier to remove from the tree than the node n, copy the item that is in m to n, remove the node m from the tree. The max number of comparisons for a retrieval, insertion or deletion is the height of the tree. The max and min heights of the binary search tree. Uses the adt binary search tree to sort an array of records into search-key order. Efficiency: average case o(n*log n, worst case o(n^2) Java: objects can be serialized to save in an file or transmit over a network: provided class implements serializable interface.