Binary Search Tree
Properties
- Left subtree
- The left subtree of a given node contains only nodes with keys lesser than the node's key.
- Right subtree
- The right subtree of a given node contains only nodes with keys greater than the node's key.
image-20210328105543998.png
Insertion
Case 1: Empty tree
- Create a new node with new key
- Make that new node root
Case 2: Non-empty Tree
- Start at the root
- Traverse the tree to find a location for the new key(stops at a leaf node X)
- Add a new node as a child of X
Deletion
Case 1 : No Children
- It is a leaf node, we don't need to worry about "disconnecting" its children.
- "Sever" the connection between the parent node and found ndoe.
- Either delete the "stray" node or let garbage collector remove it. Done!
image-20210328110520387.png
if (current.leftChid == null && current.rightChid == null){
if (current == root){
root = null;
}else if (isLeftChild){
parent.leftChid = null;
}else{
parent.rightChid = null;
}
Case 2: One Child
- It is not a leaf node, we NEED to worry about its child.
- FOUND node's only child should take it's place to preserve BST properties
- Connect FOUND node's parent to FOUND's child. "Old" connection "severed"
- Either delete the "stray" node or let garbage collector remove it. Done!
image-20210328112046132.png
else if (current.rightChid == null){
if (current == root){
root = current.rightChid;
}else if (isLeftChild){
parent.leftChid = current.leftChid;
}else{
parent.rightChid = current.rightChid;
}
}else if (current.leftChid == null){
if (current == root){
root = current.rightChid;
}else if (isLeftChild){
parent.leftChid = current.leftChid;
}else{
parent.rightChid = current.rightChid;
}
Case 3: Two Children
Successor a Leaf Node,Successor a Right Child
- It is not s leaf node, we NEED to worry about its children.
- Trick: find an IN-ORDER successor of FOUND node place it instead of FOUND
- FOUND's LEFT child also becomes FOUND's successor LEFT CHILD
- We can now "server" FOUND's connection to its LEFT child. Successor's got it.
- Now we need to connect FOUND'S Parent with FOUND'S successor
- Either delete the "stray" node or let garbage collector remove it. Done!
image-20210328113809441.png
Successor is a Left Descendant of Right Child
image-20210328114102618.png
Successor is a Left Descendant of Right Child , Successor has a Right Child
image-20210328114358375.png
