CMPT 225 Lecture Notes - Self-Balancing Binary Search Tree, Null Pointer
4 Sep 2013
School
Department
Course
Professor
Document Summary
Finding correct position when inserting is really easy, just search for the value. Then put it at the null child where you want to insert it. Also might have issues where something of that value is already in tree. Little bit of extra constant work in building new node and attaching, but very minimal. Note that whatever you insert into a tree will be a leaf. Don"t try and change internal structure of tree, although you could. Node to be deleted is a leaf (no children): remove it - assign null to parent"s reference. Node to be deleted has one child: replace the node with its sub tree. These first two cases can be kinda collapsed. (as the subtree of a leaf is null, which is what you want to give the parent anyway) Need to look ahead, and look at both children.
