Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно - исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку "Продолжить", я принимаю политику конфиденциальности

Для разделения дерева найдем наименьший элемент, больший или равный 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.