Расширяющееся дерево

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Расширяющееся дерево
Тип Дерево
Изобретено в 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 была нечётна.

Splay tree zig.svg

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

Zigzig.gif

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

Zigzag.gif

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 () {
            if (leftChild) 
                delete leftChild;
            if (rightChild) 
                delete rightChild;
            if (parent) 
                delete parent;
        }
    } * root;

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

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

        return successor;
    }

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

        if (predecessor->leftChild != nullptr) {
            predecessor = _Maximum(predecessor->leftChild);
        } else {
            while (predecessor != predecessor->parent->rightChild
                   || predecessor != root) {
                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.