Нужна помощь в расчете глубины левой и правой веток любого двоичного дерева

Question

Мне нужно написать дерево AVL для курса по структурам данных, и я застрял в расчете коэффициента баланса для поддерева, чтобы я знал, где и как вращать дерево.

Спасибо, Eric

редактирование:

Я знаю, что нужно подсчитать количество узлов в двоичном дереве.

private int countTotalNodes(AVLNode<T> start){

    AVLNode<T> current = start;

    if(current.getLeft() != null){
        return countTotalNodes(current.getLeft());
    }
    if(current.getRight() != null){
        return countTotalNodes(current.getRight());
    }
    return 1;

} 

Answer 1

Обычный подход заключается в добавлении поля коэффициента баланса в структуру данных узла дерева. Изменения коэффициента баланса происходят при вставках и удалениях, и эти изменения распространяются по мере вращения, чтобы сохранить баланс. Есть хорошее объяснение этому, с псевдокодом, здесь .

Вычисление баланса при каждой вставке или удалении (вместо того, чтобы сохранять баланс как немного дополнительной бухгалтерии на каждом узле) делает эти операции намного более дорогими.

Answer 2

Я думаю, что обычная реализация для дерева AVL хранит высоту узла в самом узле и обновляется в операциях вставки, вырезания и связывания. После этих операций мы должны проверить, верна ли высота верхних вершин, примерно так:

/**
 * Recursively updates heights starting with given node. 
 * If height of given node is already correct we know 
 * that we can stop.
 */
private void updateHeights(AvlNode<T> node){
    if(node == null) return;
    int heightLeft = node.left != null ? node.left.height : -1;
    int heightRight = node.right != null ? node.right.height : -1;
    int height = heightLeft > heightRight ? heightLeft + 1 : heightRight + 1;
    if(node.height != height){
        node.height = height;
        updateHeights(node.parent);
    }
}

Это всегда вызывается у родителя самого измененного узла, так сказать. Ах, старые добрые времена - реализация дерева AVL - это забавный маленький проект - удачи .. и тщательно протестируйте его!

Answer 3

Ваша функция подсчета для количества узлов неверна (за исключением очень вырожденных деревьев) - она ​​считает левое или правое поддерево, но никогда не учитывает оба.Попробуйте сначала исправить это.

Затем подумайте, как вы можете использовать аналогичный алгоритм для построения глубины.

---

Но, как сказано в других ответах, не используйте это для балансировкиваше дерево, так как снижение производительности будет более чем все преимущества сбалансированного дерева.Вместо этого сохраните свою глубину в узлах и подумайте, когда она должна быть адаптирована.

Answer 4

Напишите метод для расчета глубины дерева, а затем примените его к левому и правому поддеревьям.

В этом вся прелесть древовидной структуры данных: она естественно самоподобна и рекурсивна.