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

Я работаю над BST, который будет уравновешивать узлы в соответствии с их попаданиями и их элементами, где попадание - это атрибут, который увеличивается при обнаружении узла с помощью find(), contains() и т. Д. Корнем дерева является узел с наибольшим количеством просмотров. Весь мой код в порядке, кроме метода баланса, который уравновесит дерево после того, как я увеличу попадание. Я использую модифицированные методы поворота дерева AVL ( https://users.cs.fiu.edu/~weiss/dsj2/code/weiss/nonstandard/Rotations.java), где я не сравниваю элементы, а просто совпадения узел. Я не могу заставить его работать независимо от того, что я пытаюсь, я не могу заставить дерево сбалансироваться правильно. Вот мой код:

 public void balanceTree() {
    balanceTree(root);
}

private void balanceTree(Node node) {

    if (node.left.getHits() <= node.getHits() && node.right.getHits() <= node.getHits()) {
        return;
    } else if (node.left.getHits() > node.getHits()) {
        node = rotateWithLeftChild(node);

    } else if (node.right.getHits() > node.getHits()) {
        node = rotateWithRightChild(node);

    }


}

static Node rotateWithLeftChild(Node k2) {
    Node k1 = k2.left;
    k2.left = k1.right;
    k1.right = k2;
    return k1;
}

static Node rotateWithRightChild(Node k1) {
    Node k2 = k1.right;
    k1.right = k2.left;
    k2.left = k1;
    return k2;
}

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

Источник

2 ответа

Решение

В Java нельзя изменить переданный параметр, поэтому необходимо вернуть новое значение узла.

public void balanceTree() {
    root = balanceTree(root);
}

private Node balanceTree(Node node) 
    if (node.left.getHits() <= node.getHits()
            && node.right.getHits() <= node.getHits()) {
        node.left = balanceTree(node.left);
        node.right = balanceTree(node.right);
    } else if (node.left.getHits() > node.getHits()) {
        node = rotateWithLeftChild(node);
    } else if (node.right.getHits() > node.getHits()) {
        node = rotateWithRightChild(node);
    }
    return node;
}

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

Без вращения нужно возвращаться.

Текущий алгоритм рекурсирует влево, а затем вправо, но если вращение происходит слева, правое поддерево больше не может быть рекурсивно.

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

Источник

Есть 2 вещи не так с этим кодом.
1) Я скучаю по структуре этого Дерева. Таким образом, они должны быть отсортированы в зависимости от их HitCount, а не то, что в основном список / коллекция отсортирована по HitCount?

Прямо сейчас вы меняете узлы их левым и правым узлами, если у них более высокий счетчик попаданий, чем у них самого. Итак, представьте, что 2 узла [A, B] A имеют 1 hitCount, а B имеет 2 hitCount. Итак, при сортировке (вы, вероятно, будете перебирать узлы):
Начните ситуацию: [A, B]

Первая сортировка: A имеет меньшее значение HitCount, чем B, поэтому поменяйте местами с правым. Результат = [B, A]

Второй вид: A имеет меньшее значение HitCount, чем B, поэтому поменяйте местами с левой. Результат = [A, B]

Где мы заканчиваем? Лучшей идеей может быть использование List и сортировка Nodes на основе их hitCount. Таким образом, вам не придется связываться со всем этим.

2) Ваши методы обмена не работают так, как вы думаете. Внимательно посмотрите на это:

 static Node rotateWithLeftChild(Node k2) {
     Node k1 = k2.left;
     k2.left = k1.right;
     k1.right = k2;
     return k1;
 }

 // exact the same results:
 static Node rotateWithLeftChild(Node k2)
 {
     k2.left = k2;
     return k2.left;
 }

Мне не кажется правильным. Возможно, вы имели в виду что-то вроде:

 static Node rotateWithLeftChild(Node k2)
 {
     Node k1 = k2.left;
     k1.right = k2.right;
     k2.left = k1.left;
     k1.left = k2;
     k2.right = k1;
     return k1;
 }

И, конечно, обратное относится к rotateWithRightChild.

Я надеюсь, что это немного помогло вам.

Редактировать:

Как реализовать Список / Коллекция для заказа? Когда узел добавлен в дерево, просто добавьте узел в Lisf/Collection. И когда вы хотите отсортировать узлы, просто используйте это:

 //myNodesCollection is the List/Collection containing all the nodes.
 static void sortByHitCount()
 {
     Collections.sort(myNodesCollection, (n1, n2) -> n1.getHits() - n2.getHits());
 }

Это может показаться сложным, но этот метод выполняет всю сортировку за вас. Первый параметр - это список / коллекция, которую вы хотите отсортировать. Второй параметр - это компаратор, который в этом случае сравнивает каждый узел на основе их hitCount.

Документация: https://docs.oracle.com/javase/8/docs/api/java/util/Comparator.html

Источник
Другие вопросы по тегам