package edu.columbia.cs.cs1007.datastructures;
/**
* An implementation of a binary search tree (BST)
* @author Julia Stoyanovich (jds2109@columbia.edu)
* COMS 1007, Summer 2009
*
*/
public class BST {
/**
* Implementation of a private Node class
* @author Dustin
*
*/
private class Node {
// Instance fields
private int _data;
private Node _parent = null;
private Node _left = null;
private Node _right = null;
/**
* Constructor
* @param value
*/
public Node (int value) {
_data = value;
}
/**
* Constructor
* @param value
* @param parent
* @param left
* @param right
*/
public Node(int value, Node parent, Node left, Node right) {
this(value);
_parent = parent;
_left = left;
_right = right;
}
/**
* Accessor that gets the key.
* @return key
*/
public int getKey() {
return _data;
}
/**
* Accessor that gets the value.
* @return value
*/
public int getVal() {
return _data;
}
/**
* Accessor that gets the parent of a node.
* Parent may be null.
* @return parent node
*/
public Node getParent() {
return _parent;
}
/**
* Accessor that gets the left child of a node.
* Child may be null.
* @return left child node
*/
public Node getLeft() {
return _left;
}
/**
* Accessor that gets the right child of a node.
* Child may be null.
* @return right child node
*/
public Node getRight() {
return _right;
}
/**
* Mutator that sets the value.
* @param val
*/
public void setVal(int val) {
_data = val;
}
/**
* Generate a string representation of a node.
* @return string representation.
*/
public String toString() {
return " " + getVal();
}
/**
* Set right child to the supplied node.
* If the child is not null -- update the parent reference
* in the child.
* @param child
*/
public void setRight(Node child) {
this._right = child;
if (child != null) {
child._parent = this;
}
}
/**
* Set left child to the supplied node.
* If the child is not null -- update the parent reference
* in the child.
* @param child
*/
public void setLeft(Node child) {
this._left = child;
if (child != null) {
child._parent = this;
}
}
/**
* Set parent to the supplied node.
* Parent may ne null.
* @param parent
*/
public void setParent(Node parent) {
_parent = parent;
}
/**
* Insert a new node into an appropriate position in the tree.
* @param newNode
*/
public void insert(Node newNode) {
// nodes with equal key go into the left subtree
if( getKey() < newNode.getKey()) {
if (getRight() == null) {
setRight(newNode);
} else {
getRight().insert(newNode);
}
} else {
if (getLeft() == null) {
setLeft(newNode);
} else {
getLeft().insert(newNode);
}
}
}
/**
* Find the node with the lowest key.
* @return minimum node
*/
public Node min() {
if (getLeft() == null) {
return this;
}
return getLeft().min();
}
/**
* Find the node with the highest key.
* @return maximum node
*/
public Node max() {
if (getRight() == null) {
return this;
}
return getRight().max();
}
/**
* Is this node the root?
* @return true if root, false otherwise
*/
public boolean isRoot() {
return _parent == null;
}
/**
* Is this node the left child of its parent?
* @return true if left child, false otherwise
*/
public boolean isLeftChild() {
return !isRoot() && (this == getParent().getLeft());
}
/**
* Is this node the right child of its parent?
* @return true if right child, false otherwise
*/
public boolean isRightChild() {
return !isRoot() && (this == getParent().getRight());
}
}
private Node _root = null;
/**
* Constructor.
* @param inArray
*/
public BST(int[] inArray) {
for (int val : inArray) {
Node newNode = new Node(val);
insert(newNode);
}
}
/**
* Generate a string representation of the tree.
* @return string representation
*/
public String printTree() {
return printTree(_root);
}
/**
* Generate a string representation of the tree.
* @return string representation
*/
public String printTree(Node node) {
if (node == null) {
return "";
}
return printTree(node.getLeft()) + node.toString() + printTree(node.getRight());
}
/**
* Search the tree for a node with the specified key.
* @param root
* @param key
* @return Node if key is found, null otherwise.
*/
public Node search(int key) {
return search(_root, key);
}
/**
* Search the tree for a node with the specified key.
* @param root
* @param key
* @return Node if key is found, null otherwise.
*/
public Node search(Node root, int key) {
if ((root == null) || (root.getKey() == key)) {
return root;
} else if (key < root.getKey()) {
return search(root.getLeft(), key);
} else {
return search(root.getRight(), key);
}
}
/**
* Insert a node into the appropriate position in the tree
* @param newNode
*/
public void insert(Node newNode) {
if (_root == null) {
_root = newNode;
} else {
_root.insert(newNode);
}
}
/**
* Find the successor of a node.
* @param node
* @return successor node
*/
public Node succ(Node node) {
if (node.getRight() != null) {
return node.getRight().min();
} else {
while ((node.getParent() != null) &&
(node == node.getParent().getRight())) {
node = node.getParent();
}
return node.getParent();
}
}
/**
* Find the predecessor of a node.
* @param node
* @return predecessor node
*/
public Node pred(Node node) {
if (node.getLeft() != null) {
return node.getLeft().max();
} else {
while ((node.getParent() != null) &&
(node == node.getParent().getLeft())) {
node = node.getParent();
}
return node.getParent();
}
}
/**
* Find the node with the lowest key.
* @return minimum node
*/
public Node min() {
return _root.min();
}
/**
* Find the node with the highest key.
* @return maximum node
*/
public Node max() {
return _root.max();
}
/**
* Delete a node from the tree.
* @param node
*/
public void delete(Node node) {
if ((node.getLeft() == null) || (node.getRight() == null)) {
// node has fewer than 2 children
if ((node.getLeft() == null) && (node.getRight() == null)) {
// CASE 1: node has no children, just remove it
if (node.isLeftChild()) {
node.getParent().setLeft(null);
} else if (node.isRightChild()) {
node.getParent().setRight(null);
}
} else {
// CASE 2: node has exactly one child
Node child = node.getRight();
if (child == null) {
child = node.getLeft();
}
if (node.isLeftChild()) {
node.getParent().setLeft(child);
} else if (node.isRightChild()){
node.getParent().setRight(child);
} else {
// the node is a root
child.setParent(null);
_root = child;
}
}
} else {
// CASE 3: node has 2 children
Node successor = succ(node);
delete(successor); // recursive call against cases 1 or 2
node.setVal(successor.getVal());
}
}
public static void main(String[] args) {
int [] inArr = {15, 6, 18, 3, 7, 17, 20, 2, 4, 13, 9};
BST tree = new BST(inArr);
System.out.println(tree.printTree());
System.out.println("Min " + tree.min().toString());
System.out.println("Max " + tree.max().toString());
int [] keysArr = {13, 35, 15, 2, 7};
for (int val : keysArr) {
Node hit = tree.search(val);
if (hit == null) {
System.out.println("Node " + val + " not found.");
} else {
Node succ = tree.succ(hit);
if (succ!= null) {
System.out.println("succ(" + val + ") =" + succ.toString());
} else {
System.out.println(val + " has no successor");
}
Node pred = tree.pred(hit);
if (pred!= null) {
System.out.println("pred(" + val + ") = " + pred.toString());
} else {
System.out.println(val + " has no predecessor.");
}
tree.delete(hit);
System.out.println("Deleted " + val + " : " + tree.printTree());
}
}
}
}
|