WikiSort.ru - Программирование

ПОИСК ПО САЙТУ | о проекте
Расширяющееся дерево
Тип Дерево
Изобретена в 1985
Создатель Дэниел Слитор и Роберт Андре Тарьян
Сложность в О-символике
В среднем В худшем случае
Расход памяти O(n) O(n)
Поиск O(log n) O(log n)
Вставка O(log n) O(log n)
Удаление O(log n) O(log n)

Расширяющееся (англ. splay tree) или косое дерево является двоичным деревом поиска, в котором поддерживается свойство сбалансированности. Это дерево принадлежит классу «саморегулирующихся деревьев», которые поддерживают необходимый баланс ветвления дерева, чтобы обеспечить выполнение операций поиска, добавления и удаления за логарифмическое время от числа хранимых элементов. Это реализуется без использования каких-либо дополнительных полей в узлах дерева (как, например, в Красно-чёрных деревьях или АВЛ-деревьях, где в вершинах хранится, соответственно, цвет вершины и глубина поддерева). Вместо этого «расширяющие операции» (splay operation), частью которых являются вращения, выполняются при каждом обращении к дереву.

Учётная стоимость (англ.) в расчёте на одну операцию с деревом составляет .

Расширяющееся дерево придумали Роберт Тарьян и Даниель Слейтор в 1983 году.

Операции

Splay (расширение)

Основная операция дерева. Заключается в перемещении вершины в корень при помощи последовательного выполнения трёх операций: Zig, Zig-Zig и Zig-Zag. Обозначим вершину, которую хотим переместить в корень за x, её родителя — p, а родителя p (если существует) — g.

Zig: выполняется, когда p является корнем. Дерево поворачивается по ребру между x и p. Существует лишь для разбора крайнего случая и выполняется только один раз в конце, когда изначальная глубина x была нечётна.

Zig-Zig: выполняется, когда и x, и p являются левыми (или правыми) сыновьями. Дерево поворачивается по ребру между g и p, а потом — по ребру между p и x.

Zig-Zag: выполняется, когда x является правым сыном, а p — левым (или наоборот). Дерево поворачивается по ребру между p и x, а затем — по ребру между x и g.

Search (поиск элемента)

Поиск выполняется как в обычном двоичном дереве поиска. При нахождении элемента запускаем Splay для него.

Insert (добавление элемента)

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

Delete (удаление элемента)

Находим элемент в дереве, делаем Splay для него, делаем текущим деревом Merge его детей.

Merge (объединение двух деревьев)

Для слияния деревьев T1 и T2, в которых все ключи T1 меньше ключей в T2, делаем Splay для максимального элемента T1, тогда у корня T1 не будет правого ребенка. После этого делаем T2 правым ребенком T1.

Split (разделение дерева на две части)

Для разделения дерева найдем наименьший элемент, больший или равный x, и сделаем для него Splay. После этого отрезаем у корня левого ребёнка и возвращаем 2 получившихся дерева.

Реализация

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

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

#ifndef SPLAYTREE_H
#define SPLAYTREE_H

template<typename T> class SplayTree {
private:
    struct SplayNode {
        Node * leftChild;
        Node * rightChild
        Node * parent;
        T data;

        Node (const T & key = T()) 
        : leftChild(nullptr), rightChild(nullptr), parent(nullptr), key(key) {}

        ~Node () {
                delete leftChild;
                delete rightChild;
                delete parent;
        }
    } * root;

private:
    SplayNode * _Successor(SplayNode * localRoot) const {
        SplayNode * successor = localRoot;

        if (successor->rightChild != nullptr) {
            successor = _Minimum(successor->rightChild);
        } else {
            while (successor != root
                    || successor != successor->parent->leftChild) {
                successor = successor->parent;
            }
        }

        return successor;
    }

    SplayNode * _Predecessor(SplayNode * localRoot) const {
        SplayNode * predecessor = localRoot;

        if (predecessor->leftChild != nullptr) {
            predecessor = _Maximum(predecessor->leftChild);
        } else {
            while (predecessor != root
                   || predecessor != predecessor->parent->rightChild) {
                predecessor = predecessor->parent;
            }
        }

        return predecessor;
    }

    SplayNode * _Minimum(SplayNode * localRoot) const {
        SplayNode * minimum = localRoot;

        while (minimum != nullptr) 
            minimum = minimum->leftChild;
        
        return minimum;
    }

    SplayNode * _Maximum(SplayNode * localRoot) const {
        SplayNode * maximum = localRoot;

        while (maximum != nullptr) 
            maximum = maximum->rightChild;

        return maximum;
    }

    SplayNode * _Search(const T & key) {
        SplayNode * searchedElement = root;

        while (searchedElement != nullptr) {
            if (searchedElement->data < key) 
                searchedElement = searchedElement->rightChild;
            else if (key < searchedElement->data) 
                searchedElement = searchedElement->leftChild;
            else if (searchedElement->data == key) {
                _Splay(searchedElement);
                return searchedElement;
            }
        }

        return nullptr;
    }

    void _LeftRotate(SplayNode * localRoot) {
        SplayNode * rightChild = localRoot->rightChild;

        localRoot->rightChild = rightChild->leftChild;
        if (rightChild->leftChild != nullptr) 
            rightChild->leftChild->parent = localRoot;

        _Transplant(localRoot, rightChild);

        rightChild->leftChild = localRoot;
        rightChild->leftChild->parent = rightChild;
    }

    void _RightRotate(SplayNode * localRoot) {
        SplayNode * leftChild = localRoot->leftChild;

        localRoot->leftChild = leftChild->rightChild;
        if (leftChild->rightChild != nullptr) 
            leftChild->rightChild->parent = localRoot;

        _Transplant(localRoot, leftChild);

        leftChild->rightChild = localRoot;
        leftChild->rightChild->parent = leftChild;
    }

    void _Transplant(SplayNode * localParent, SplayNode * localChild) {
        if (localParent->parent == nullptr) 
            root = localChild;
        else if (localParent == localParent->parent->leftChild) 
            localParent->parent->leftChild = localChild;
        else if (localParent == localParent->parent->rightChild) 
            localParent->parent->rightChild = localChild;

        if (localChild != nullptr)
            localChild->parent = localParent->parent;
    }

    void _Splay(SplayNode * pivotElement) {
        while (pivotElement != root) {
            if (pivotElement->parent == root) {

                if (pivotElement == pivotElement->parent->leftChild) 
                    _RightRotate(pivotElement);
                else if (pivotElement == pivotElement->parent->rightChild) {
                    _LeftRotate(pivotElement);

            } else {
                // Zig-Zig step.
                if (pivotElement == pivotElement->parent->leftChild &&
                    pivotElement->parent == pivotElement->parent->parent->leftChild) {

                    _RightRotate(pivotElement->parent->parent);
                    _RightRotate(pivotElement->parent);

                } else if (pivotElement == pivotElement->parent->rightChild &&
                           pivotElement->parent == pivotElement->parent->parent->rightChild) {

                    _LeftRotate(pivotElement->parent->parent);
                    _LeftRotate(pivotElement->parent);
                }
                // Zig-Zag step.
                else if (pivotElement == pivotElement->parent->rightChild &&
                    pivotElement->parent == pivotElement->parent->parent->leftChild) {

                    _LeftRotate(pivotElement->parent);
                    _RightRotate(pivotElement->parent->parent);

                } else if (pivotElement == pivotElement->parent->leftChild &&
                           pivotElement->parent == pivotElement->parent->parent->rightChild) {

                    _RightRotate(pivotElement->parent);
                    _LeftRotate(pivotElement->parent->parent);
                }
            }
        }
    }
    
public:
    SplayTree() { root = nullptr; }

    virtual ~SplayTree() { delete root; }

    void Insert(const T & key) {
        SplayNode * preInsertPlace = nullptr;
        SplayNode * insertPlace = root;

        while (insertPlace != nullptr) {
            preInsertPlace = insertPlace;

            if (insertPlace->data() < key) 
                insertPlace = insertPlace->rightChild;
            else if (key < insertPlace->data) {
                insertPlace = insertPlace->leftChild;
        }

        SplayNode * insertElement = new SplayNode(key);
        insertElement->parent = preInsertPlace;

        if (preInsertPlace == nullptr) 
            root = insertElement;
        else if (preInsertPlace->data < insertElement->data) 
            preInsertPlace->rightChild = insertElement;
        else if (insertElement->data < preInsertPlace->data) 
            preInsertPlace->leftChild = insertElement;

        _Splay(insertElement);
    }

    void Remove(const T & key) {
        SplayNode * removeElement = _Search(key);

        if (removeElement != nullptr) {
            if (removeElement->rightChild == nullptr) 
                _Transplant(removeElement, removeElement->leftChild);
            else if (removeElement->leftChild == nullptr) 
                _Transplant(removeElement, removeElement->leftChild);
            else {
                SplayNode * newLocalRoot = _Minimum(removeElement->rightChild);

                if (newLocalRoot->parent != removeElement) {

                    _Transplant(newLocalRoot, newLocalRoot->rightChild);

                    newLocalRoot->rightChild = removeElement->rightChild;
                    newLocalRoot->rightChild->parent = newLocalRoot;
                }

                _Transplant(removeElement, newLocalRoot);

                newLocalRoot->leftChild = removeElement->leftChild;
                newLocalRoot->leftChild->parent = newLocalRoot;

                _Splay(newLocalRoot);
            }

            delete removeElement;
        }
    }

    bool Search(const T &key) { return _Search(key) != nullptr; }

    bool isEmpty() const { return root == nullptr; }

    T Successor(const T & key) {
        if (_Successor(_Search(key)) != nullptr) {
            return _Successor(_Search(key))->getValue();
        } else {
            return -1;
        }
    }

    T Predecessor(const T & key) {
        if (_Predecessor(_Search(key)) != nullptr) {
            return _Predecessor(_Search(key))->getValue();
        } else {
            return -1;
        }
    }
};

#endif //SPLAYTREE_H

Примечание

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

Расширяющееся дерево не обладает никакими явными функциями балансировки, но процесс скоса узлов к корню способствует поддержанию дерева в сбалансированном виде.

См. также

  • Сбалансированные (самобалансирующиеся) деревья:

Литература

  • Томас Х. Кормен и др. Алгоритмы: построение и анализ. — 2-е изд. М.: Издательский дом «Вильямс», 2007. — С. 1296. ISBN 5-8459-0857-4.
  • Daniel Sleator, Robert Tarjan. A data structure for dynamic trees. — Journal of Computer and System Sciences, 1983. — С. 262-391.

Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".

Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.

Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .




Текст в блоке "Читать" взят с сайта "Википедия" и доступен по лицензии Creative Commons Attribution-ShareAlike; в отдельных случаях могут действовать дополнительные условия.

Другой контент может иметь иную лицензию. Перед использованием материалов сайта WikiSort.ru внимательно изучите правила лицензирования конкретных элементов наполнения сайта.

2019-2024
WikiSort.ru - проект по пересортировке и дополнению контента Википедии