private void performRebalance(Stack nodeTrace) {
        Node n = (Node) nodeTrace.pop();
        Node parent;

        do {
            if (nodeTrace.size() == 0) {
                parent = null;
            } else {
                parent = (Node) nodeTrace.pop();
            }

            //RebalanceIndex berechnen
            RebalanceIndex rebalanceIndex = getRebalanceIndex(n);

            if (rebalanceIndex != RebalanceIndex.BALANCED) {
                //Baum rebalancieren, wenn er nicht balanciert ist
                Node rebalanced = null;

                switch (rebalanceIndex) {
                    case LEFTLEFT:
                        rebalanced = rotateLeftLeft(n);
                        break;
                    case RIGHTRIGHT:
                        rebalanced = rotateRightRight(n);
                        break;
                    case LEFTRIGHT:
                        rebalanced = rotateLeftRight(n);
                        break;
                    case RIGHTLEFT:
                        rebalanced = rotateRightLeft(n);
                        break;
                }

                //Subtree durch neuen rebalancierten Subtree ersetzen
                if (parent == null) {
                    root = rebalanced;
                } else if (n == parent.getLft()) {
                    parent.setLft(rebalanced);
                } else {
                    parent.setRgt(rebalanced);
                }
            }

            n = parent;
        } while (parent != null);
    }