Create a gist now

Instantly share code, notes, and snippets.

Binary Search Tree implementation
public class BinarySearchTree {
private Node root;
public BinarySearchTree() {
this.root = null;
}
public BinarySearchTree(Node root) {
this.root = root;
}
public void insert(Node x) {
Node y = null;
Node z = root;
while (z != null) {
y = z;
if (x.getKey() <= z.getKey()) {
z = z.getLeftChild();
} else {
z = z.getRightChild();
}
}
x.setParent(y);
if (root == null) {
root = x;
} else if (x.getKey() <= y.getKey()) {
y.setLeftChild(x);
} else {
y.setRightChild(x);
}
}
public void inorderTreeWalk(Node x) {
if (x != null) {
inorderTreeWalk(x.getLeftChild());
System.out.println(x.getKey());
inorderTreeWalk(x.getRightChild());
}
}
public void preorderTreeWalk(Node x) {
if (x != null) {
System.out.println(x.getKey());
preorderTreeWalk(x.getLeftChild());
preorderTreeWalk(x.getRightChild());
}
}
public void postorderTreeWalk(Node x) {
if (x != null) {
postorderTreeWalk(x.getLeftChild());
postorderTreeWalk(x.getRightChild());
System.out.println(x.getKey());
}
}
public Node treeMinimum(Node x) {
while (x.getLeftChild() != null) {
x = x.getLeftChild();
}
return x;
}
public Node treeMaximum(Node x) {
while (x.getRightChild() != null) {
x = x.getRightChild();
}
return x;
}
public Node treePredecessor(Node x) {
if (x.getLeftChild() != null) {
return treeMaximum(x.getLeftChild());
}
Node parent = x.getParent();
while (parent != null && parent.getKey() > x.getKey()) {
parent = parent.getParent();
}
return parent;
}
public Node treeSuccessor(Node x) {
if (x.getRightChild() != null) {
return treeMinimum(x.getRightChild());
}
Node parent = x.getParent();
while (parent != null && parent.getRightChild() == x) {
x = parent;
parent = x.getParent();
}
return parent;
}
/**
* Searches a node starting to traverse from root.
*
* @param x
* @param key
* @return
*/
public Node search(Node x, int key) {
while (x != null && key != x.getKey()) {
if (key < x.getKey()) {
x = x.getLeftChild();
} else {
x = x.getRightChild();
}
}
return x;
}
public void delete(int key) {
Node delNode = search(root, key);
if (delNode.getLeftChild() == null) {
transplant(delNode, delNode.getRightChild());
} else if (delNode.getRightChild() == null) {
transplant(delNode, delNode.getLeftChild());
} else {
Node y = treePredecessor(delNode);
swapKeys(delNode, y);
TreeNode z = pre.getLeft();
if (y.getParent().getLeftChild() == y) {
y.getParent().setLeftChild(z);
} else {
y.getParent().setRightChild(z);
}
}
}
public int getHeight(Node x) {
if (x == null) {
return 0;
}
int left = 0;
int right = 0;
if (x.getLeftChild() != null) {
left = getHeight(x.getLeftChild()) + 1;
}
if (x.getRightChild() != null) {
right = getHeight(x.getRightChild()) + 1;
}
return Math.max(left, right);
}
public boolean isBalanced(Node x) {
if (x == null) {
return false;
}
int leftDepth = getHeight(x.getLeftChild());
int rightDepth = getHeight(x.getRightChild());
if (Math.abs(leftDepth - rightDepth) <= 1 && isBalanced(x.getLeftChild()) && isBalanced(x.getRightChild())) {
return true;
} else {
return false;
}
}
private void swapKeys(Node delNode, Node y) {
int temp = delNode.getKey();
delNode.setKey(y.getKey());
y.setKey(temp);
}
private void transplant(Node u, Node v) {
if (u.getParent() == null) { // we delete the root
root = v;
} else if (u.getParent().getLeftChild() == u) {
u.getParent().setLeftChild(v);
} else {
u.getParent().setRightChild(v);
}
if (v != null) {
v.setParent(u.getParent());
}
}
public Node getRoot() {
return this.root;
}
}
public class Node {
private Node leftChild;
private Node rightChild;
private Node parent;
private int key;
public Node(int key) {
this.key = key;
}
public Node getLeftChild() {
return leftChild;
}
public void setLeftChild(Node leftChild) {
this.leftChild = leftChild;
}
public Node getRightChild() {
return rightChild;
}
public void setRightChild(Node rightChild) {
this.rightChild = rightChild;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public void setKey(int key) {
this.key = key;
}
public int getKey() {
return key;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment