package algodataufg04_j;

public class BinST {

    public int key;
    public BinST left = null;
    public BinST right = null;
    public BinST root = null;

    public BinST() {
    }

    public BinST(int x) {
        this.key = x;
    }

    public BinST(int x, BinST l, BinST r) {
        this.key = x;
        this.right = r;
        this.left = l;
    }

    public void insert(int x) {
        if (root == null) {
            root = new BinST(x, null, null);
        } else {
            insert(x, root);
        }
    }

    private void insert(int x, BinST n) {
        if (x == n.key) { // pruefen auf bereits vorhandenen Key
            System.out.println("Key already in tree...");
            return;
        } else if (x < n.key) { // X kleiner als Key?
            if (n.left == null) { // links kein Key vorhanden, dann erzeuge Key
                n.left = new BinST(x);
            } else { // rekursiver Aufruf der Methode insert
                insert(x, n.left);
            }
        } else if (x > n.key) { // X groesser als Key?
            if (n.right == null) { // rechts kein Key vorhanden, dann erzeuge Key
                n.right = new BinST(x);
            } else { // rekursiver Aufruf der Methode insert
                insert(x, n.right);
            }
        }
    }

    public void insertIt(int x) { //Neues Element nicht rekursiv einf�gen
        BinST runner = root;

        for (;;) {
            if (x > runner.key) { // X groe�er als Key
                if (runner.right != null) { // Rechter Key vorhanen
                    runner = runner.right; // Anf�gen rechts
                } else { //Existiert nicht, anf�gen
                    runner.right = new BinST(x, null, null); // neuer Key anf�gen
                    return;
                }
            } else if (x < runner.key) { // X kleienr als Key
                if (runner.left != null) { // linker Key vorhanden
                    runner = runner.left; // rechts anf�gen
                } else { //Existiert nicht, anf�gen
                    runner.left = new BinST(x, null, null);
                    return;
                }
            } else if (x == runner.key) { // Element existiert schon
                System.out.println("Key already in tree...");
                return;
            }
        }
    }

    public int size(BinST n) {
        if (n == null) { // kein Element vorhanden
            return 0;
        } else if ((n.left == null) && (n.right == null)) { // nur root vorhanden
            return 1;
        } else {
            int l = size(n.left);
            int r = size(n.right);
            return ((l <= r) ? (l + 1) : (r + 1)); // Wenn l <= r dann l+1 ansonsten r+1
        }
    }

    public int countNodes(BinST n) {
        if (n == null) {
            return 0;
        } else {
            int count = 1;
            count += countNodes(n.left); // rekursiver Aufruf der Methode
            count += countNodes(n.right); // rekursiver Aufruf der Methode

            return count;
        }
    }

    public int countN(int x) {
        return countNodes(find(x, root));
    }

    public void find(int k) {
        if (root == null) {
            return;
        } else {
            find(k, root);
        }
    }

    private BinST find(int k, BinST node) {
        if (k == node.key) {
            return node;
        } else if ((k < node.key) && node.left != null) {
            return find(k, node.left);
        } else if (node.right != null) {
            return find(k, node.right);
        } else {
            return null;
        }
    }

    public int getParent(int x) {
        return getParent(x, root).key;
    }

    private BinST getParent(int x, BinST node) {
        if (node == null) // leerer Baum
        {
            return null;
        }
        if ((node.key == x) && (node == root)) // Key = Wurzel
        {
            return null;
        } else if (((node.right != null) && (node.right.key == x)) || ((node.left != null) && (node.left.key == x))) { // Key = Parent
            return node;
        } else if (x < node.key) { // rekursiver Aufruf
            return getParent(x, node.left);
        } else if (node.right != null) { // rekursiver Aufruf
            return getParent(x, node.right);
        } else {
            return null;
        }
    }

    public int hoehe(int x) {
        return size(find(x, root)) + 1;
    }

    public BinST smallestInSubtree() {
        if (left != null) {
            return left.smallestInSubtree();
        } else {
            return this;
        }
    }

    public void delete(int k) {
        if (root == null) {
            System.out.println("The tree is empty...");
            return;
        } else {
            delete(k, root);
        }
    }

    private BinST delete(int k, BinST node) {
        //zu l�schenden Knoten suchen
        if (node == null) {
            return node;
        } else if (k < node.key) {
            node.left = delete(k, node.left);
        } else if (k > node.key) {
            node.right = delete(k, node.right);
        } else if (node.left != null && node.right != null) {
            //Knoten gefunden, hat 2 kinder
            node.key = node.right.smallestInSubtree().key;
            node.right = delete(node.key, node.right);
        } else {
            //Knoten hat ein Kind, oder keines
            if (node.left != null) {
                node = node.left;
            } else {
                node = node.right;
            }
        }
        return node;
    }

    public void lwr(final BinST w) {
        if (w != null) {
            lwr(w.left);
            System.out.print(w.key + " ");
            lwr(w.right);
        }
    }

    public void rwl(final BinST w) {
        if (w != null) {
            rwl(w.right);
            System.out.print(w.key + " ");
            rwl(w.left);
        }
    }

    public void rwlGraph(final BinST w, int depth, char LWR) {
        if (w != null) {
            rwlGraph(w.right, ++depth, 'R');
            for (int i = 0; i < depth; i++) {
                System.out.print("   ");
            }
            switch (LWR) {
                case 'L':
                    System.out.print("\\");
                    break;
                case 'W':
                    System.out.print(" ");
                    break;
                case 'R':
                    System.out.print("/");
            }
            System.out.println(w.key);
            rwlGraph(w.left, depth, 'L');
        }
    }

    public void wrl(final BinST w) {
        if (w != null) {
            System.out.print(w.key + " ");
            wrl(w.right);
            wrl(w.left);
        }
    }

    public void lrw(final BinST w) {
        if (w != null) {
            lrw(w.left);
            lrw(w.right);
            System.out.print(w.key + " ");
        }
    }

    public void rlw(final BinST w) {
        if (w != null) {
            rlw(w.right);
            rlw(w.left);
            System.out.print(w.key + " ");
        }
    }

    public void wlr(final BinST w) {
        if (w != null) {
            System.out.print(w.key + " ");
            wlr(w.left);
            wlr(w.right);
        }
    }

    /* ====== Linksrotation ====== */
    public void rotateLeft(int x) {
        rotateLeft(x, root);
    }

    private void rotateLeft(int x, BinST n) {
        if (n == null) {
            System.out.println("Knoten nicht gefunden");
        } else {
            if (x < n.key) {
                rotateLeft(x, n.left);
            } else if (x > n.key) {
                rotateLeft(x, n.right);
            } else if (x == n.key) {
                if (n.right == null) {
                    System.out.println("Keinen Knoten zum tauschen gefunden...");
                    return;
                } else {
                    if (n == root) {
                        root = n.right;
                    }
                    BinST nparent = n.getParent(n.key, root);
                    BinST goesDown = n;
                    BinST toSwitch = n.right.left;
                    n = n.right;
                    if (nparent != null) {
                        if (nparent.key > goesDown.key) {
                            nparent.left = n;
                        } else if (nparent.key < goesDown.key) {
                            nparent.right = n;
                        }
                    }
                    n.left = goesDown;
                    n.left.right = toSwitch;
                }
            }
        }
    }

    /* ====== Rechtsrotation ====== */
    public void rotateRight(int x) {
        rotateRight(x, root);
    }

    private void rotateRight(int x, BinST n) {
        if (n == null) {
            System.out.println("Knoten nicht gefunden");
        } else {
            if (x < n.key) {
                rotateRight(x, n.left);
            } else if (x > n.key) {
                rotateRight(x, n.right);
            } else if (x == n.key) {
                if (n.left == null) {
                    System.out.println("Keinen Knoten zum Tauschen gefunden");
                    return;
                } else {
                    if (n == root) {
                        root = n.left;
                    }
                    BinST nparent = n.getParent(n.key, root);
                    BinST goesDown = n;
                    BinST toSwitch = n.left.right;
                    n = n.left;
                    if (nparent != null) {
                        if (nparent.key > goesDown.key) {
                            nparent.left = n;
                        } else if (nparent.key < goesDown.key) {
                            nparent.right = n;
                        }
                    }
                    n.right = goesDown;
                    n.right.left = toSwitch;
                }
            }
        }
    }

    /* ======== Doppelrotation ======= */
    public void doubleRotate(int x) {
        rotateLeft(x);
        rotateRight(x);
    }
}