Skip to content

Instantly share code, notes, and snippets.

@TwoTau
Last active November 28, 2018 22:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save TwoTau/646343374e9addd82206f3f823081feb to your computer and use it in GitHub Desktop.
Save TwoTau/646343374e9addd82206f3f823081feb to your computer and use it in GitHub Desktop.
Ayy this is the Best Tree implementation
import java.util.Scanner;
public class BestTree<E extends Comparable<E>> {
private TreeNode overallRoot;
public BestTree(TreeNode root) {
overallRoot = root;
}
public BestTree() {
this(null);
}
// Adds the given element to the tree in sorted order
public void addSorted(E data) {
overallRoot = addSorted(overallRoot, data);
}
private TreeNode addSorted(TreeNode root, E data) {
if (root == null) return new TreeNode(data);
int compareTo = data.compareTo(root.data);
if (compareTo < 0) { // data <= root
root.left = addSorted(root.left, data);
} else if (compareTo > 0) { // data > root
root.right = addSorted(root.right, data);
}
return root;
}
private void remove(E data) {
overallRoot = remove(overallRoot, data);
}
private TreeNode remove(TreeNode root, E data) {
System.out.println(" / " + root);
if (root == null) return null;
int compareTo = data.compareTo(root.data);
if (compareTo < 0) { // data < root
root.left = remove(root.left, data);
} else if (compareTo > 0) { // data > root
root.right = remove(root.right, data);
} else { // data == root, have to delete this node
if (root.left == null && root.right == null) {
return null;
} else if (root.left == null && root.right != null) {
return root.right;
} else if (root.left != null && root.right == null) {
return root.left;
} else { // has both left and right nodes
Object[] removeMin = removeMin(root.right);
root.right = (TreeNode) removeMin[0];
root.data = (E) removeMin[1];
}
}
return root;
}
private Object[] removeMin(TreeNode root) {
if (root.left == null) {
Object[] result = new Object[2] {
root,
root.data
};
return result;
}
}
// returns whether the tree contains the given value,
// only works if this is a binary search tree.
public boolean contains(E value) {
return contains(overallRoot, value);
}
private boolean contains(TreeNode root, E value) {
if (root == null) return false;
if (value.compareTo(root.data) < 0) return contains(root.left, value);
if (value.compareTo(root.data) > 0) return contains(root.right, value);
return true;
}
public void fillToDepth(int depth, E defaultValue) {
overallRoot = fillToDepth(overallRoot, depth, defaultValue);
}
private TreeNode fillToDepth(TreeNode root, int depth, E defaultValue) {
if (depth > 0) {
if (root == null) return new TreeNode(defaultValue);
root.left = fillToDepth(root.left, depth - 1, defaultValue);
root.right = fillToDepth(root.right, depth - 1, defaultValue);
}
return root;
}
// Prints contents of tree through in-order traversal
public String toString() {
return nodeToString(overallRoot).substring(1);
}
private String nodeToString(TreeNode root) {
return (root == null) ? "" : nodeToString(root.left) + "." +
root.data.toString() + nodeToString(root.right);
}
public void printSideways() {
printSideways(overallRoot, 0);
}
private void printSideways(TreeNode root, int depth) {
String indentation = new String(new char[depth]).replace("\0", "....");
if (root != null) {
printSideways(root.right, depth + 1);
System.out.println(indentation + root.data);
printSideways(root.left, depth + 1);
}
}
public static void main(String[] args) {
System.out.println("Best Tree v1.0\n==============\n");
BestTree<Integer> tree = new BestTree<Integer>();
tree.addSorted(25);
for (int i = 0; i < 10; i++) {
tree.addSorted((int) (Math.random() * 50 + 1));
}
// tree.fillToDepth(4, -1);
System.out.println("In order: " + tree);
System.out.println("Tree: " + tree);
System.out.println("\nSideways Tree:");
tree.printSideways();
Scanner input = new Scanner(System.in);
System.out.print("Delete: ");
while (input.hasNextInt()) {
int n = input.nextInt();
tree.remove(n);
tree.printSideways();
System.out.print("\nDelete: ");
}
}
private class TreeNode {
public E data;
public TreeNode left;
public TreeNode right;
public TreeNode(E data, TreeNode left, TreeNode right) {
this.data = data;
this.left = left;
this.right = right;
}
public TreeNode(E data) {
this(data, null, null);
}
public String toString() {
return "(" + data.toString() + ")";
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment