Балансировка дерева двоичного поиска - PullRequest
Новая
       22

Балансировка дерева двоичного поиска

1 голос
/ 23 марта 2010

У меня был квестон, но он не спас. У меня проблемы с балансировкой полностью несбалансированного дерева (узлы 1-15 по правой стороне).

У меня проблемы с переполнением стека. 

> // balancing
    public void balance(node n) {
        if(n != null) {
            System.out.println(height(n)-levels);
            if (height(n.RCN) != height(n.LCN)) {
                if (height(n.RCN) > height(n.LCN)) {
                    if(height(n.RCN) > height(n.LCN)) {
                        n = rotateL(n);
                        n = rotateR(n);
                    } else {
                        n = rotateL(n);
                    }
                } else {
                    if(height(n.LCN) > height(n.RCN)) {
                        n = rotateR(n);
                        n = rotateL(n);
                    } else {
                        n = rotateR(n);
                    }
                }
                balance(n.LCN);
                balance(n.RCN);
            }
        }
    }

    // depth from node to left
    public int heightL(node n) {
        if (n == null)
            return 0;
        return height(n.LCN) + 1;
    }

    // depth from node from the right
    public int heightR(node n) {
        if (n == null)
            return 0;
        return height(n.RCN) + 1;
    }

    // left rotation around node
    public node rotateL(node n) {
        if (n == null)
            return null;
        else {
            node newRoot = n.RCN;
            n.RCN = newRoot.LCN;
            newRoot.LCN = n;
            return newRoot;
        }
    }

    // right rotation around node
    public node rotateR(node n) {
        if (n == null)
            return null;
        else {
            node newRoot = n.LCN;
            n.LCN = newRoot.RCN;
            newRoot.RCN = n;
            return newRoot;
        }
    }

1 Ответ

1 голос
/ 23 марта 2010

Выполнение rotateL с последующим rotateR в конечном итоге ничего не делает, так как вы модифицируете тот же самый узел.n не оригинал n.Это newNode от функции.В общем, n выглядит примерно так: 

newNode = rotateL(n);
n = rotateR(newNode);

Таким образом, вы в основном оставляете дерево без изменений.

Я также не уверен, почему вы повторяете проверку if (height(n.RCN) > height(n.LCN)).Я думаю, вы имели в виду, что ваша первая проверка больше похожа на abs(height(n.RCN) - height(n.LCN)) > 1, а затем используйте сравнение, чтобы определить, какой способ поворота.

Кроме того, не могли бы вы добавить реализацию для height(...)?

...