Левое вращение в красно-черных деревьях

Я просматривал Red Black Trees, описанные в «Алгоритмах» Роберта Седжвика. Вот код для вставки в красное черное дерево.

public void put(Key key, Value val) {
    root = put(root, key, val);
    root.color = BLACK;
    assert check();
}

// insert the key-value pair in the subtree rooted at h
private Node put(Node h, Key key, Value val) { 
    if (h == null) return new Node(key, val, RED, 1);

    int cmp = key.compareTo(h.key);
    if      (cmp < 0) h.left  = put(h.left,  key, val); 
    else if (cmp > 0) h.right = put(h.right, key, val); 
    else              h.val   = val;

    // fix-up any right-leaning links
    if (isRed(h.right) && !isRed(h.left))      h = rotateLeft(h);
    if (isRed(h.left)  &&  isRed(h.left.left)) h = rotateRight(h);
    if (isRed(h.left)  &&  isRed(h.right))     flipColors(h);
    h.N = size(h.left) + size(h.right) + 1;

    return h;
}

Вот изображение для визуализации красно-черного исправления. redblackvisualizationРассмотрим случай, когда вставляемый элемент находится в середине верхнего 3-узла. Мы должны выполнить три операции, указанные в трех операторах if, а именно: h=rotateLeft(h), h=rotateRight(h) и flipcolors(h). Проблема в том, что когда мы назначаем h = rotateLeft(h). возвращенный узел является указателем на средний узел из трех узлов с двумя последовательными левыми красными ссылками. Но алгоритм предполагает, что возвращенный узел является верхним узлом в 3 узлах с двумя последовательными левыми красными ссылками. Итак, когда мы снова rotateRight(h), мы оказываемся в той же позиции, с которой начали. Может я не понял алгоритма.

Вот код для rotateLeft(h)

private Node rotateLeft(Node h) {
    assert (h != null) && isRed(h.right);
    Node x = h.right;
    h.right = x.left;
    x.left = h;
    x.color = x.left.color;
    x.left.color = RED;
    x.N = h.N;
    h.N = size(h.left) + size(h.right) + 1;
    return x;
}

Пожалуйста, помогите мне понять, как h=rotateLeft(h) дает верхний узел вместо среднего узла в трех узлах с двумя последовательными красными левыми ссылками.


java algorithm red-black-tree
person Shikhar Subedi    schedule 31.10.2013    source источник
comment
Вероятно, вы можете обрезать изображение, чтобы просто показать визуализацию, если только текст не имеет большого значения.   -  person Bernhard Barker    schedule 31.10.2013
comment
текст не имеет значения. я обрежу изображение.   -  person Shikhar Subedi    schedule 31.10.2013

Ответы (1)


arrow_upward
1
arrow_downward

Наконец-то я понял, как работает алгоритм. после h=rotateLeft(h) второй и третий if statements оцениваются как false. и h возвращается. На один уровень вверх по рекурсии мы получаем h.left =h, где h слева от равенства — это узел верхнего уровня из трех узлов с двумя последовательными красными левыми ссылками. Затем первый оператор if оценивается как ложный, второй оператор if оценивается как истинный, и мы делаем поворот вправо, затем мы меняем цвета.

Пожалуйста, поправьте меня, если я ошибаюсь.

person Shikhar Subedi    schedule 31.10.2013