CSC148H5 Lecture Notes - Lecture 20: Binary Search Tree, University Of Toronto Mississauga, Init
28 Feb 2017
School
Department
Course
Professor
Document Summary
Csc148h5s - introduction to computer science (winter 2017) We have seen two ways to represent trees. We"ll use a form of nodes and references to represent a bst. We"ll use a btnode class to represent a node in the bst. We"ll use a bs t class to represent the tree itself. The bst class has a root attribute that is. A reference to the root btnode of the tree. Depends on the where the node exists in the tree. We must be able to delete the node without violating the bst property. To delete a node with a single child, cut out that node. When a node has two children, it may not be correct to move one of the children up eg. removing 4 in the example below. To delete a node with two children, replace it by its predecessor. This yields a new bst that cannot violate the bst property.
