Bst с определенными характеристиками; Bst, который удерживает узлы с несколькими взаимодействиями на root - PullRequest
Новая
       6

Bst с определенными характеристиками; Bst, который удерживает узлы с несколькими взаимодействиями на root

0 голосов
/ 09 апреля 2020

Мне нужно реализовать особый тип BST, который: удерживает узлы с несколькими взаимодействиями в верхней части. В частности: 1 Каждый раз, когда ключ K вставляется или ищется в дереве, он перемещается в root (сохраняя свойство быть BST) через последовательность операций всплытия, называемых CLIMB. 2 Если элемент K ищется в FST и обнаруживается в данном узле N, к нему применяется операция CLIMB. Если элемент K отсутствует, операция применяется к листу, на котором заканчивается поиск. 3 Если узел удален, операция CLIMB применяется к родительскому узлу удаленного узла.

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

Но я не могу реализовать. Может кто-нибудь мне помочь? Я уверен, что для эксперта это мелочь, но для меня это кошмар.

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

Я не понимаю, как перемещать части дерева

Справка.

1 Ответ

0 голосов
/ 09 апреля 2020

Предположим, мы звоним climb(n). Удалите поддерево с n как root из дерева и поместите его как новый root. К сожалению, мы не можем поместить все старое дерево в любого потомка n и назвать его днем.

Единственное, что мы можем точно сказать, это то, что если [l, u] - это диапазон значений, хранящихся в поддереве с root n, то все узлы за пределами этого поддерева l ie за пределами этот диапазон. Это относится ко всем поддеревьям на самом деле. Здесь, однако, также кроется суть вашего подхода: вы предполагаете, что все значения в «старом дереве» l ie на одной стороне этого диапазона, хотя на самом деле их можно расположить вокруг этого диапазона. Т.е. представьте, что вы вызываете climb на левом дочернем элементе правого дочернего элемента root (7): 

                        5
            3                     8
           ...                7        9
           ...             6             ...

Независимо от того, на какой стороне узла 7 вы разместите 5, это будет неправильно. Либо 5, либо 8 должны быть не на месте.

Используя этот факт, мы можем откатиться от parent(n), пока не достигнем старого root и поместить все поддеревья, встречающиеся на пути в новом дереве, используя стандартный BST- insert: 

climb(n):
    // get the new-root and remove it from the tree rooted at old_root
    old_root = root(n)
    new_root = n
    remove_node(old_root, n)

    // iterate ancestors of n up to root
    node = parent(n)
    while node != nil do
        // remove current ancestor (node) from the original tree
        next = parent(node)
        remove_child(parent(node), node)

        // insert node into the new tree (all nodes that are still appended remain children of node)
        insert_node(new_root, node)
        node = next
    done

    return new_root

Благодаря вышеупомянутому правилу о диапазонах, это будет выдавать действительный BST после каждой итерации. Однако в каждой итерации новое поддерево будет добавлено как самый правый дочерний элемент самого правого листа или самый левый дочерний элемент самого левого листа дерева с корнем в new_root, так что это может быть хорошей идеей для перебалансировать поддеревья с корнями в left_child(new_root) и right_child(new_root), так как дерево довольно скоро станет довольно несбалансированным.

...