Форма входа

Наша реклама

Помогите сайту просмотрите рекламу

Поиск

Календарь

«  Март 2024  »
ПнВтСрЧтПтСбВс
    123
45678910
11121314151617
18192021222324
25262728293031

Наш опрос

Оцените мой сайт
Всего ответов: 122

Статистика


Онлайн всего: 1
Гостей: 1
Пользователей: 0




Четверг, 28.03.2024, 13:23
Приветствую Вас Гость | RSS
Скорая помощь для студентов
Главная | Регистрация | Вход
Лекция 11


   insertFixup(x);

    return(x);

}

 void deleteFixup(Node *x) {

     /*************************************

    *  maintain Red-Black tree balance  *

    *  after deleting node x            *

    *************************************/

     while (x != root && x->color == BLACK) {

        if (x == x->parent->left) {

            Node *w = x->parent->right;

            if (w->color == RED) {

                w->color = BLACK;

                x->parent->color = RED;

                rotateLeft (x->parent);

                w = x->parent->right;

            }

            if (w->left->color == BLACK && w->right->color == BLACK) {

                w->color = RED;

                x = x->parent;

            } else {

                if (w->right->color == BLACK) {

                    w->left->color = BLACK;

                    w->color = RED;

                    rotateRight (w);

                    w = x->parent->right;

                }

                w->color = x->parent->color;

                x->parent->color = BLACK;

                w->right->color = BLACK;

                rotateLeft (x->parent);

                x = root;

            }

        } else {

            Node *w = x->parent->left;

            if (w->color == RED) {

                w->color = BLACK;

                x->parent->color = RED;

                rotateRight (x->parent);

                w = x->parent->left;

            }

            if (w->right->color == BLACK && w->left->color == BLACK) {

                w->color = RED;

                x = x->parent;

            } else {

                if (w->left->color == BLACK) {

                    w->right->color = BLACK;

                    w->color = RED;

                    rotateLeft (w);

                    w = x->parent->left;

                }

                w->color = x->parent->color;

                x->parent->color = BLACK;

                w->left->color = BLACK;

                rotateRight (x->parent);

                x = root;

            }

        }

    }

    x->color = BLACK;

}

 void deleteNode(Node *z) {

    Node *x, *y;

     /*****************************

    *  delete node z from tree  *

    *****************************/

     if (!z || z == NIL) return;

      if (z->left == NIL || z->right == NIL) {

        /* y has a NIL node as a child */

        y = z;

    } else {

        /* find tree successor with a NIL node as a child */

        y = z->right;

        while (y->left != NIL) y = y->left;

    }

     /* x is y's only child */

    if (y->left != NIL)

        x = y->left;

    else

        x = y->right;

     /* remove y from the parent chain */

    x->parent = y->parent;

    if (y->parent)

        if (y == y->parent->left)

            y->parent->left = x;

        else

            y->parent->right = x;

    else

        root = x;

     if (y != z) z->data = y->data;

     if (y->color == BLACK)

        deleteFixup (x);

     free (y);

}

 Node *findNode(T data) {

     /*******************************

    *  find node containing data  *

    *******************************/

     Node *current = root;

    while(current != NIL)

        if(compEQ(data, current->data))

            return (current);

        else

            current = compLT (data, current->data) ?

                current->left : current->right;

    return(0);

}

 Дополнительно Слоёные списки

Слоёные списки - это связные списки, которые позволяют вам пропустить (skip) ненужные элементы, прыгнув сразу к нужному. Это позволяет преодолеть ограничения последовательного поиска, являющегося основным источником неэффективного поиска в списках. В то же время вставка и удаление остаются сравнительно эффективными. Оценка среднего времени поиска в таких списках есть O(lg n). Для наихудшего случая оценкой является O(n), но худший случай крайне маловероятен. Отличное введение в слоёные списки вы найдете у Пью [1990] [Pugh].

Теория

Идея, лежащая в основе слоёных списков, очень напоминает метод, используемый при поиске имен в адресной книжке. Чтобы найти имя, вы помечаете буквой страницу, откуда начинаются имена, начинающиеся с этой буквы. На рис. 3.8, например, самый верхний список представляет обычный односвязный список. Добавив один "уровень" ссылок, мы ускорим поиск. Сначала мы идем по ссылкам уровня 1, затем, когда дойдем по нужного отрезка списка, пойдем по ссылкам нулевого уровня.

Рис. 3.8. Устройство слоёного списка

Эта простая идея может быть расширена - мы можем добавить нужное число уровней. Внизу на рис. 3.8 мы видим второй уровень, который позволяет двигаться еще быстрее первого. При поиске элемента мы двигаемся по этому уровню, пока не дойдем до нужного отрезка списка. Затем мы еще уменьшаем интервал неопределенности, двигаясь по ссылкам 1-го уровня. Лишь после этого мы проходим по ссылкам 0-го уровня.Вставляя узел, мы должны будем определить количество исходящих от него ссылок. Эта проблема легче всего решается с использованием случайного механизма: при добавлении нового узла мы "бросаем монету", чтобы определить, нужно ли добавлять еще уровень. Например, мы можем добавлять очередные уровни до тех пор, пока выпадает "решка". Если реализован только один уровень, мы имеем дело фактически с обычным списком и время поиска есть O(n). Однако, если имеется достаточное число уровней, слоёный список можно считать деревом с корнем на высшем уровне, а для дерева время поиска есть O(lg n).Поскольку реализация слоёных списков включает в себя случайный процесс, для времени поиска в них устанавливаются вероятностные границы. При обычных условиях эти границы довольно узки. Например, когда мы ищем элемент в списке из 1000 узлов, вероятность того, что время поиска окажется в 5 раз больше среднего, можно оценить как 1/1,000,000,000,000,000,000. 


Copyright MyCorp © 2024