Красно-черное дерево - Как найти родителя узла?

Question

В красно-черном дереве при вращении необходимо знать, кто является родителем определенного узла.Однако узел имеет ссылку только на правого или левого потомка.

Я думал дать переменной экземпляра узла "parent", но по этой причине я не думаю, что это стоит делать, а также было бы слишком сложно изменить родительскую ссылку за оборот.

public class Node {
  private left;
  private right;
  private isRed;
  private parent; //I don't think this is good idea
}

Итак, мое решение - написать метод findParent (), который использует поиск для поиска родителя.Мне интересно, есть ли другой способ найти родителя узла?

Мое решение:

образец дерева:

    50
    / \
   25  75

Если вы хотите найти родителя узла25, вы передаете что-то вроде:

Node parent = findParent(Node25.value);

и он возвращает node50.

protected Node findParent(int val) {
        if(root == null) {
            return null;
        }
        Node current = root;
        Node parent = current;
        while(true) {
            if(current.val == val) { //found
                return parent;
            }
            if(current == null) { //not found
                return null;
            }
            parent = current;
            if(current.val > val) { //go left
                current = current.left;
            }
            else { //go right
                current = current.right; 
            }
        }
    }

Answer 1

Я думал дать переменной экземпляра узла "parent", но по этой причине я не думаю, что это стоит делать

Чтобы у ваших узлов была ссылка parent, требуется один дополнительный указатель / ссылка на узел. Сравните это с необходимостью обходить дерево всякий раз, когда вам нужно знать родителя для данного узла.

Это тогда компромисс между

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

Я думаю, что выбор между этими двумя вариантами несколько субъективен, но лично я бы предпочел просто отслеживать ссылки parent.

Для справки: java.util.TreeMap реализован в виде красно-черного дерева, в котором Entry узлов содержат ссылки left, right и parent.

Answer 2

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

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

Answer 3

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

Answer 4

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

Предположим, кто-то хочет вставить 23 в следующее дерево:

Красное черное дерево

Обычно алгоритм для вставки:

1. Найти узел, где 23 будет, если он находится в дереве

2. Если 23 уже существует, вернуть ошибку

3. Если 23 еще не существует, поместите его туда.

4. Запустите процедуру перебалансировки / окраски по мере необходимости.

Теперь, чтобыиспользуя подход стека, вы выделяете стек, достаточно большой, чтобы поддерживать один узел на уровень вашего дерева (я думаю, что 2 * Ceiling (Log2 (count)) + 2) должны вас охватить.Вы могли бы даже сохранить стек, выделенный для вставки или удаления, и просто очищать его каждый раз, когда начинаете вставку.

Итак - посмотрите на корень.Вставьте его в стек.23 больше значения в корне, так что идите направо.Теперь поместите текущий узел (значение 21) в стек.Если 23 находится в дереве, оно должно быть справа от текущего узла.Но узел справа от текущего узла является нулевым сторожем.Таким образом, этот null-sentinel должен быть заменен узлом с вашим значением.Родитель - это элемент в верхней части стека (последний раз помещен в стек), дедушка - следующий в очереди ... и т. Д. Так как вы, кажется, изучаете ... Java предоставляет интерфейс стека для вас, поэтому вам не понадобитсяразработать свой собственный стек, чтобы сделать это.Просто используйте их.

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

Answer 5

Использование родительского указателя необязательно. Если вы откажетесь от родительского указателя, вам придется писать операции вставки / удаления с использованием рекурсии (рекурсивные вызовы методов сохраняют родительскую информацию в стеке) или писать итеративную версию, которая поддерживает свой собственный стек родителей при перемещении по дереву.

Очень хорошее описание красно-черных деревьев можно найти здесь

http://adtinfo.org/

Включает описания ряда реализаций rbtree, в том числе с родительскими указателями и без них.

Если вы хотите сэкономить место (и это достаточно справедливо), действительно отличное описание реализации rbtree можно найти здесь

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_rbtree.aspx

Метод, который вы описали для поиска родителя узла, был бы очень неэффективным, если бы он использовался реализациями вставки / удаления. Используйте указатель или используйте рекурсию.