COMS W3134 Lecture Notes - Lecture 12: Avl Tree, True Value, Binary Search Tree
Document Summary
Insert: public driver method that just takes in value. Inserting element into binary search tree, either root remains unchanged, or root will change. Returns root of new tree after it has been inserted: private recursive method that takes in value and root. Base case searches for x, if found then nothing to insert, if not then place it hanging off a leaf node. If root node passed in is null, then need to instantiate new node then return that node compareto again to see if x should be inserted to the left or right sub-tree. Return t, which is a node findmin: keep going left if not empty, the invoke findmin on root of the tree. If t. left == null then return t, otherwise keep recursion. There is no minimum if there"s nothing in the tree, so throw underflowexception if isempty() in public method: again have public and private methods findmax, keep going right.