public class Node
{
private int data;
private Node left;
private Node right;
private Node parent;
public Node()
{
data = 0;
left = null;
right = null;
parent = null;
}
public Node(int e)
{
data = e;
left = null;
right = null;
parent = null;
}
public int getData()
{
return data;
}
public Node getLeft()
{
return left;
}
public Node getRight()
{
return right;
}
public Node getParent()
{
return parent;
}
public void setData(int d)
{
data = d;
}
public void setLeft(Node l)
{
left = l;
}
public void setRight(Node r)
{
right = r;
}
public void setParent(Node p)
{
parent = p;
}
}
public class BST
{
private Node root;
/** Initialize a tree
*/
public BST()
{
root = null;
}
/** Return the root of the tree
* @return {@code Node}, root of tree
*/
// O(1)
public Node getRoot()
{
return root;
}
/** Set a node for root
* @param Node, node
* @return none
*/
// O(1)
public void setRoot(Node n)
{
root = n;
}
/** Check if the tree is an empty tree
* @return {@code bool}, tree if tree is empty; false otherwise
*/
// O(1)
public boolean isEmpty()
{
return (root == null);
}
/** Get the size of the tree
* @return {@code int}, number of elements in tree
*/
// O(n)
public int size()
{
return getSize(root);
}
public int getSize(Node n)
{
if(n == null) return 0;
return 1+getSize(n.getLeft())+getSize(n.getRight());
}
/** Check if two trees are same
* @param BST a binary search tree
* @return {@code bool}, tree if two trees are same; false otherwise
*/
// O(n)
public boolean equals(BST t)
{
if(size() != t.size()) return false;
return nodeEquals(root, t.root);
}
public boolean nodeEquals(Node n1, Node n2)
{
if(n1 == null && n2 == null) return true;
if(n1 == null && n2 != null) return false;
if(n1 != null & n2 == null) return false;
if(n1.getData() != n2.getData()) return false;
return nodeEquals(n1.getLeft(), n2.getLeft()) && nodeEquals(n1.getRight(), n2.getRight());
}
/** Print elements in ascending ord
*/
// O(n)
public void inorderWalk()
{
if(root != null) printLDR(root);
System.out.println();
}
public void printLDR(Node n)
{
if(n == null) return;
printLDR(n.getLeft());
System.out.printf("%5d", n.getData());
printLDR(n.getRight());
}
/** Print element in pre-order
*/
// O(n)
public void preorderWalk()
{
if(root != null) printDLR(root);
System.out.println();
}
public void printDLR(Node n)
{
if(n == null) return;
System.out.printf("%5d", n.getData());
printDLR(n.getLeft());
printDLR(n.getRight());
}
/** Print elements in post-order
*/
// O(n)
public void postorderWalk()
{
if(root != null) printLRD(root);
System.out.println();
}
public void printLRD(Node n)
{
if(n == null) return;
printLRD(n.getLeft());
printLRD(n.getRight());
System.out.printf("%5d", n.getData());
}
/** Insert an element into the tree with the algorithm in CLRS
* @param, int value of inserting element
*/
// O(lgn)
public void insert(int e)
{
if(search(e)) return;
Node parent = null;
Node current = root;
while(current != null)
{
parent = current;
current = (e < current.getData())?parent.getLeft():parent.getRight();
}
Node temp = new Node(e);
temp.setParent(parent);
if(parent == null)
root = temp;
else
{
if (e < parent.getData())
parent.setLeft(temp);
else
parent.setRight(temp);
}
}
/** Replace a subtree with other subtree
* @param u target subtree
* @param v replace subtree
*/
// O(1)
public void transplant(Node u, Node v)
{
if(u.getParent() == null)
root = v;
else if(u == u.getParent().getLeft())
u.getParent().setLeft(v);
else
u.getParent().setRight(v);
if(v != null)
v.setParent(u.getParent());
}
/** Delete an element in tree
* @param int value of an element
*/
// O(lgn)
public void delete(int e)
{
if(!search(e)) return;
Node z = searchNode(root, e);
//z has no child or only one child
if(z.getLeft() == null)
transplant(z, z.getRight());
else if(z.getRight() == null)
transplant(z, z.getLeft());
//z has two children
else
{
Node y = getMin(z.getRight());
if(y.getParent() != z)//y is not z's child
{
transplant(y, y.getRight());
y.setRight(z.getRight());
y.getRight().setParent(y);
}
transplant(z, y);
y.setLeft(z.getLeft());
y.getLeft().setParent(y);
}
}
/** Get the successor of an element in tree
* @param int value of the element
* @return {@code int}, value of successor
*/
// O(lgn)
public int successor(int e)
{
Node n = getSuccessor(root, e);
if (n == null) return -1;
return n.getData();
}
public Node getSuccessor(Node n, int e)
{
if(!search(e))
return null;
Node target = searchNode(n, e);
//if the right subtree of node is nonempty
if(target.getRight() != null)
return getMin(target.getRight());
Node p = target.getParent();
//if node is leave, the right subtree is empty
while (p != null && target == p.getRight()) {
target = p;
p = p.getParent();
}
return p;
}
/** Get the predecessor of an element in tree
* @param int value of the element
* @return {@code int}, value of predecessor
*/
// O(lgn)
public int predecessor(int e)
{
Node n = getPredecessor(root, e);
if (n == null) return -1;
return n.getData();
}
public Node getPredecessor(Node n, int e)
{
if(!search(e))
return null;
Node target = searchNode(n, e);
//if the left subtree of node is nonempty
if(target.getLeft() != null)
return getMax(target.getLeft());
Node p = target.getParent();
//if node is leave, the left subtree is empty
while(p != null && target == p.getLeft()){
target = p;
p = p.getParent();
}
return p;
}
/** Get the height of the tree
*/
// O(lgn)
public int height()
{
return getHeight(root);
}
public int getHeight(Node n)
{
if(n == null) return 0;
if(n.getLeft() == null && n.getRight() == null)
return 1;
int l = getHeight(n.getLeft());
int r = getHeight(n.getRight());
return (l>r)?(1+l):(1+r);
}
/** Search an element in tree
* @param int, the value of an element
* @return {@code boolean}, true if the tree contains the element and false otherwise
*/
// O(lgn)
public boolean search(int e)
{
return searchNode(root, e) != null;
}
public Node searchNode(Node n, int e)
{
if(n == null) return null;
if(n.getData() == e) return n;
if(e < n.getData())
return searchNode(n.getLeft(), e);
else
return searchNode(n.getRight(), e);
}
/** Get the minimum element in tree
* @param none
* @return {@code int}, value of the minimum element in tree
*/
// O(lgn)
public int min()
{
Node n = getMin(root);
return n.getData();
}
public Node getMin(Node n)
{
if(n.getLeft() == null)
return n;
return getMin(n.getLeft());
}
/** Get the maximum element in tree
* @param none
* @return int, value of the maximum element in tree
*/
// O(lgn)
public int max()
{
Node n = getMax(root);
return n.getData();
}
public Node getMax(Node n)
{
if(n.getRight() == null)
return n;
return getMax(n.getRight());
}
}
public class BSTTest
{
public static void main(String args[])
{
BST t = new BST();
// Create tree
t.insert(8);
t.insert(3);
t.insert(10);
t.insert(1);
t.insert(6);
t.insert(14);
t.insert(4);
t.insert(7);
t.insert(13);
t.insert(15);
// Display tree
t.inorderWalk();
// Search
System.out.println(t.search(7));//true
System.out.println(t.search(20));//false
// Min
System.out.println("Min: "+t.min());//1
// Max
System.out.println("Max: "+t.max());//15
// Height
System.out.println("Height: "+t.height());//4
// Successor
System.out.println("Successor: "+t.successor(3));//4
System.out.println("Successor: "+t.successor(7));//8
System.out.println("Successor: "+t.successor(8));//10
System.out.println("Successor: "+t.successor(15));//-1
// Predecessor
System.out.println("Predecessor: "+t.predecessor(13));//10
System.out.println("Predecessor: "+t.predecessor(10));//8
System.out.println("Predecessor: "+t.predecessor(8));//7
System.out.println("Predecessor: "+t.predecessor(1));//-1
//delete
t.delete(3);
t.inorderWalk();
}
}
