Binary Search Trees
Lecture Notes – V. Matos – CIS265
Tree-Node Class (BSTnode)
packagecsu.matos;
publicclassBSTnode<E extends Comparable<E> > {
//class variables [data, parent, left, right]
E data;
BSTnode<E> left;
BSTnode<E> right;
BSTnode<E> parent;
//constructor
publicBSTnode(E data) {
this.data = data;
this.left = null;
this.right = null;
this.parent = null;
}
//accessors
public E getData() {
returndata;
}
publicvoidsetData(E data) {
this.data = data;
}
publicBSTnode<E> getLeft() {
returnleft;
}
publicvoidsetLeft(BSTnode<E> left) {
this.left = left;
}
publicBSTnode<E> getRight() {
returnright;
}
publicvoidsetRight(BSTnode<E> right) {
this.right = right;
}
publicBSTnode<E> getParent() {
returnparent;
}
publicvoidsetParent(BSTnode<E> parent) {
this.parent = parent;
}
public String showData() {
return"BSTnode \n\t" + this
+ "\n\t[data=\t" + data
+ "\n\t,left=\t" + left
+ "\n\t,right=\t" + right
+ "\n\t,parent=" + parent
+ " ]";
}
}
BSTree Class
packagecsu.matos;
importjava.util.ArrayList;
publicclassBSTree <E extends Comparable<E> > {
BSTnode<E> root;
//------
publicBSTree() {
root = null;
}
//------
publicBSTnode<E> getRoot() {
returnroot;
}
publicvoidsetRoot(BSTnode<E> root) {
this.root = root;
}
//------
publicBSTnode<E> add( E data ){
BSTnode<E> ptrCurrent = null;
BSTnode<E> ptrPrevious = null;
booleancomingFromLeftBranch = false;
//is the tree empty?
if (root == null){
root = newBSTnode<E>(data);
returnnewBSTnode<E>(data);
}
//jump to the left or the right
ptrCurrent = root;
while ( ptrCurrent != null ){
ptrPrevious = ptrCurrent;
if(ptrCurrent.getData().compareTo(data) > 0){
//continue searching on the left side
comingFromLeftBranch = true;
ptrCurrent = ptrCurrent.getLeft();
}else {
//continue searching on the right side
comingFromLeftBranch = false;
ptrCurrent = ptrCurrent.getRight();
}
}
//time to attach the newNode to the tree
BSTnode<E> newNode = newBSTnode<E>(data);
newNode.setParent(ptrPrevious);
if(comingFromLeftBranch){
ptrPrevious.setLeft(newNode);
}else{
ptrPrevious.setRight(newNode);
}
returnnewNode;
}
//------
publicvoidpreOrder() {
System.out.println("PRE-ORDER\t");
preOrder(root);
System.out.println();
}
//------
privatevoidpreOrder(BSTnode<E> ptr) {
if (ptr != null){
System.out.print(" " + ptr.getData());
preOrder(ptr.getLeft());
preOrder(ptr.getRight());
}
}
//------
publicvoidinOrder() {
System.out.println("IN-ORDER\t");
inOrder(root);
System.out.println();
}
//------
privatevoidinOrder(BSTnode<E> ptr) {
if (ptr != null){
inOrder(ptr.getLeft());
System.out.print(" " + ptr.getData());
inOrder(ptr.getRight());
}
}
// ------
publicvoidpostOrder() {
System.out.println("POST-ORDER\t");
postOrder(root);
System.out.println();
}
privatevoidpostOrder(BSTnode<E> ptr) {
if (ptr != null){
postOrder(ptr.getLeft());
postOrder(ptr.getRight());
System.out.print(" " + ptr.getData());
}
}
// ------
publicvoidbfsOrder() {
System.out.println("BFS-ORDER\t");
ArrayListBSTnode<E> > queue = newArrayList>();
queue.add(root);
while(queue.size() > 0 ){
BSTnode<E> ptr = queue.remove(0);
System.out.print(" " + ptr.getData());
if(ptr.getLeft() != null) queue.add(ptr.getLeft());
if(ptr.getRight() != null) queue.add(ptr.getRight());
}
}//bfsOrder
//------
publicBSTnode<E> search(E data){
BSTnode<E> ptrCurrent = null;
//is the tree empty?
if (root == null){
returnnull;
}
ptrCurrent = root;
while (ptrCurrent != null) {
if (ptrCurrent.getData().compareTo(data) > 0) {
// continue searching on the left side
ptrCurrent = ptrCurrent.getLeft();
} elseif (ptrCurrent.getData().compareTo(data) < 0) {
// continue searching on the right side
ptrCurrent = ptrCurrent.getRight();
} else {
//there is match here!
returnptrCurrent;
}
}
returnnull;
}
//------
publicboolean delete (E data ){
BSTnode<E> ancestor;
BSTnode<E> ptrToBeDeleted = search(data);
System.out.println("\nDELETE " + data + "\t" + ptrToBeDeleted);
if ( ptrToBeDeleted == null ){
returnfalse;
}
// ------
// common data
ancestor = ptrToBeDeleted.getParent();
BSTnode<E> ptrSuccessor = successorOf(ptrToBeDeleted);
// ------
//case1: node to be deleted has no children
if(ptrToBeDeleted.getLeft()==null
ptrToBeDeleted.getRight()==null){
if (ptrToBeDeleted==root){
//remove root (lonely node)
root = null;
returntrue;
}
//node is a terminal leave
if(isLeftChild( ancestor, ptrToBeDeleted)){
ancestor.setLeft(null);
}else {
ancestor.setRight(null);
}
returntrue;
}
//case2: node to be deleted has descendants
if(ptrToBeDeleted.getLeft()==null){
//case3: deleted node has no left children
if(ptrToBeDeleted==root){
//removing root having a right branch (but no left)
root = ptrSuccessor;
root.setParent(null);
returntrue;
}
//case4: deleted node is not root & has right descendants
if(isLeftChild(ancestor, ptrToBeDeleted) ){
ancestor.setLeft(ptrSuccessor);
ptrSuccessor.setParent(ancestor);
}else {
ancestor.setRight(ptrSuccessor);
ptrSuccessor.setParent(ancestor);
}
returntrue;
}
//case5: node to be deleted has LEFT descendants
if(ptrToBeDeleted.getLeft()!=null){
//remember that successor node has no right children
BSTnode<E> beforeSuccessor = ptrSuccessor.getParent();
BSTnode<E> afterSuccessor = ptrSuccessor.getLeft();
ptrToBeDeleted.setData(ptrSuccessor.getData() );
if (ptrSuccessor==ptrToBeDeleted.getLeft() ){
ptrToBeDeleted.setLeft(ptrSuccessor.getLeft());
if(afterSuccessor!=null)
afterSuccessor.setParent(beforeSuccessor);
}else {
beforeSuccessor.setRight(afterSuccessor);
if(afterSuccessor!=null){
afterSuccessor.setParent(beforeSuccessor);
}
}
returntrue;
}
returnfalse;
}//delete
//------
privatebooleanisLeftChild(BSTnode<E> parentNode, BSTnode<E> childNode) {
//SAME AS: parentNode.getData() >= childNode.getData()
if (parentNode.getData().compareTo(childNode.getData())>=0)
returntrue;
else
returnfalse;
}
// ------
publicBSTnode<E> successorOf (BSTnode<E> ptrCurrent) {
//no left subtree
if(ptrCurrent.getLeft() == null )
returnptrCurrent.getRight();
//looking for biggest rightmost node
ptrCurrent = ptrCurrent.getLeft();
BSTnode<E> ptrPrevious = ptrCurrent;
while(ptrCurrent != null){
ptrPrevious = ptrCurrent;
ptrCurrent = ptrCurrent.getRight();
}
returnptrPrevious;
}
//------
publicvoidshowData() {
System.out.println("\nBSTree [root=" + root + "]" );
}
}
Test Class
packagecsu.matos;
publicclass Driver5 {
publicstaticvoid main(String[] args) {
Integer[] sampleData = {4,2,6,1,3,5,7};
//{55, 22, 11, 33, 77, 66, 88, 44, 20, 40, 5, 18, 67, 4, 19 };
BSTree<Integer> tree = newBSTree>();
for(Integer n : sampleData){
tree.add(n);
}
tree.preOrder();
tree.postOrder();
tree.bfsOrder();
tree.delete(5);
tree.preOrder();
}
}
Console
PRE-ORDER
4 2 1 3 6 5 7
POST-ORDER
1 3 2 5 7 6 4
BFS-ORDER
4 2 6 1 3 5 7
DELETE 4csu.matos.BSTnode@15db9742
PRE-ORDER
3 2 1 6 5 7