Splay-дерево

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

Учётная стоимость в расчёте на одну операцию с деревом составляет O ( log ⁡ n ) {displaystyle O(log n)} .

Расширяющееся дерево придумали Роберт Тарьян и Даниель Слейтор в 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; } } * 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->leftChild != nullptr) minimum = minimum->leftChild; return minimum; } SplayNode * _Maximum(SplayNode * localRoot) const { SplayNode * maximum = localRoot; while (maximum->rightChild != 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->parent); else if (pivotElement == pivotElement->parent->rightChild) { _LeftRotate(pivotElement->parent); } } 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); } else if (pivotElement == pivotElement->parent->leftChild && pivotElement->parent == pivotElement->parent->parent->rightChild) { _RightRotate(pivotElement->parent); _LeftRotate(pivotElement->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->rightChild); 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