Skip to content

Instantly share code, notes, and snippets.

@tzafrir

tzafrir/gist:3738184

Created September 17, 2012 15:59
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save tzafrir/3738184 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save tzafrir/3738184 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. tzafrir created this gist Sep 17, 2012.
    110 changes: 110 additions & 0 deletions gistfile1.java
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,110 @@
    public class Main {
    public static void main(String args[]) {
    Tree<Integer> t = new Tree<Integer>();
    t.insert(20, 20);
    t.insert(10, 11);
    t.insert(40, 13);
    t.insert(30, 13);
    t.insert(25, 13);
    System.out.println(t);
    t.remove(30);
    System.out.println(t);
    }
    }

    class Tree<T> {
    int key;
    T value;
    Tree<T> left;
    Tree<T> right;
    public Tree(){};

    public void insert(int key, T value) {
    if (this.value == null) {
    this.key = key;
    this.value = value;
    } else {
    if (key < this.key) {
    if (left == null) {
    left = new Tree<T>();
    }
    left.insert(key, value);
    } else {
    if (right == null) {
    right = new Tree<T>();
    }
    right.insert(key, value);
    }
    }
    }

    public T get(int key) {
    if (this.value == null) {
    return null;
    } else if (this.key == key) {
    return value;
    } else if (key < this.key && left != null) {
    return left.get(key);
    } else if (key >= this.key && right != null) {
    return right.get(key);
    } else {
    return null;
    }
    }

    private Tree<T> getMinTree() {
    if (value != null) {
    if (left != null) {
    return left.getMinTree();
    } else {
    return this;
    }
    }
    return null;
    }

    public void remove(int key) {
    if (this.value == null) {
    return;
    }
    if (this.key == key) {
    if (left == null && right == null) {
    this.value = null;
    return;
    }
    Tree<T> s;
    if (left == null && right != null) {
    s = right;
    } else if (right == null && left != null) {
    s = left;
    } else {
    Tree<T> minTree = right.getMinTree();
    int tmpKey = minTree.key;
    T tmpVal = minTree.value;
    minTree.key = this.key;
    minTree.value = this.value;
    this.key = tmpKey;
    this.value = tmpVal;
    minTree.remove(key);
    return;
    }
    this.key = s.key;
    this.value = s.value;
    this.left = s.left;
    this.right = s.right;
    } else {
    if (key < this.key && left != null) {
    left.remove(key);
    } else if (key >= this.key && right != null) {
    right.remove(key);
    }
    }
    }

    public String toString() {
    if (value == null) {
    return "{}";
    }
    return "{" + key + ": [" + (left != null ? left.toString() : "null") + ", " + (right != null ? right.toString() : "null") + "]}";
    }
    }