Главная страница
Навигация по странице:

  • Удаление ключей

  • ответы сессия довгалюк 2 семестр. Определение Правосторонний бинарный поиск


    Скачать 3.01 Mb.
    НазваниеОпределение Правосторонний бинарный поиск
    Анкорответы сессия довгалюк 2 семестр
    Дата10.02.2022
    Размер3.01 Mb.
    Формат файлаdocx
    Имя файлаAlgoritmy.docx
    ТипДокументы
    #357616
    страница8 из 11
    1   2   3   4   5   6   7   8   9   10   11

    Вставка ключей



    Вставка нового ключа в АВЛ-дерево выполняется, по большому счету, так же, как это делается в простых деревьях поиска: спускаемся вниз по дереву, выбирая правое или левое направление движения в зависимости от результата сравнения ключа в текущем узле и вставляемого ключа. Единственное отличие заключается в том, что при возвращении из рекурсии (т.е. после того, как ключ вставлен либо в правое, либо в левое поддерево, и это дерево сбалансировано) выполняется балансировка текущего узла. Строго доказывается, что возникающий при такой вставке дисбаланс в любом узле по пути движения не превышает двух, а значит применение вышеописанной функции балансировки является корректным.

    node* insert(node* p, int k) // вставка ключа k в дерево с корнем p

    {

    if( !p ) return new node(k);

    if( k
    key )

    p->left = insert(p->left,k);

    else

    p->right = insert(p->right,k);

    return balance(p);

    }


    Чтобы проверить соответствие реализованного алгоритма вставки теоретическим оценкам для высоты АВЛ-деревьев, был проведен несложный вычислительный эксперимент. Генерировался массив из случайно расположенных чисел от 1 до 10000, далее эти числа последовательно вставлялись в изначально пустое АВЛ-дерево и измерялась высота дерева после каждой вставки. Полученные результаты были усреднены по 1000 расчетам. На следующем графике показана зависимость от n средней высоты (красная линия); минимальной высоты (зеленая линия); максимальной высоты (синяя линия). Кроме того, показаны верхняя и нижняя теоретические оценки.

    Видно, что для случайных последовательностей ключей экспериментально найденные высоты попадают в теоретические границы даже с небольшим запасом. Нижняя граница достижима (по крайней мере в некоторых точках), если исходная последовательность ключей является упорядоченной по возрастанию.

    Удаление ключей



    С удалением узлов из АВЛ-дерева, к сожалению, все не так шоколадно, как с рандомизированными деревьями поиска. Способа, основанного на слиянии (join) двух деревьев, ни найти, ни придумать не удалось. П оэтому за основу был взят вариант, описываемый практически везде (и который обычно применяется и при удалении узлов из стандартного двоичного дерева поиска). Идея следующая: находим узел p с заданным ключом k (если не находим, то делать ничего не надо), в правом поддереве находим узел min с наименьшим ключом и заменяем удаляемый узел p на найденный узел min.

    При реализации возникает несколько нюансов. Прежде всего, если у найденный узел p не имеет правого поддерева, то по свойству АВЛ-дерева слева у этого узла может быть только один единственный дочерний узел (дерево высоты 1), либо узел p вообще лист. В обоих этих случаях надо просто удалить узел p и вернуть в качестве результата указатель на левый дочерний узел узла p.

    Пусть теперь правое поддерево у p есть. Находим минимальный ключ в этом поддереве. По свойству двоичного дерева поиска этот ключ находится в конце левой ветки, начиная от корня дерева. Применяем рекурсивную функцию:

    node* findmin(node* p) // поиск узла с минимальным ключом в дереве p

    {

    return p->left?findmin(p->left):p;

    }


    Еще одна служебная функция у нас будет заниматься удалением минимального элемента из заданного дерева. Опять же, по свойству АВЛ-дерева у минимального элемента справа либо подвешен единственный узел, либо там пусто. В обоих случаях надо просто вернуть указатель на правый узел и по пути назад (при возвращении из рекурсии) выполнить балансировку. Сам минимальный узел не удаляется, т.к. он нам еще пригодится.

    node* removemin(node* p) // удаление узла с минимальным ключом из дерева p

    {

    if( p->left==0 )

    return p->right;

    p->left = removemin(p->left);

    return balance(p);

    }


    Теперь все готово для реализации удаления ключа из АВЛ-дерева. Сначала находим нужный узел, выполняя те же действия, что и при вставке ключа:

    node* remove(node* p, int k) // удаление ключа k из дерева p

    {

    if( !p ) return 0;

    if( k < p->key )

    p->left = remove(p->left,k);

    else if( k > p->key )

    p->right = remove(p->right,k);


    Как только ключ k найден, переходим к плану Б: запоминаем корни q и r левого и правого поддеревьев узла p; удаляем узел p; если правое поддерево пустое, то возвращаем указатель на левое поддерево; если правое поддерево не пустое, то находим там минимальный элемент min, потом его извлекаем оттуда, слева к min подвешиваем q, справа — то, что получилось из r, возвращаем min после его балансировки.

    else // k == p->key

    {

    node* q = p->left;

    node* r = p->right;

    delete p;

    if( !r ) return q;

    node* min = findmin(r);

    min->right = removemin(r);

    min->left = q;

    return balance(min);

    }


    При выходе из рекурсии не забываем выполнить балансировку:

    return balance(p);

    }


    Вот собственно и все! Поиск минимального узла и его извлечение, в принципе, можно реализовать в одной функции, при этом придется решать (не очень сложную) проблему с возвращением из функции пары указателей. Зато можно сэкономить на одном проходе по правому поддереву.

    1   2   3   4   5   6   7   8   9   10   11


    написать администратору сайта