Отображение структуры данных дерева

Самооптимизирующееся двоичное дерево поиска

Введение

Расширенное дерево — это структура данных, которая была изобретена профессорами компьютерных наук Дэниелом Слейтором и Робертом Тарьяном в 1985 году.

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

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

Преимущества расширенного дерева

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

Эта самооптимизация более эффективна после последовательности операций, чем сбалансированное по весу или высоте дерево, такое как дерево AVL. Поскольку деревья AVL статичны при поиске, элемент, который никогда не искался, может оставаться в верхней части дерева, в то время как элемент, который искали миллионы раз, может оставаться на 50 уровнях в дереве. Кроме того, расширенные деревья проще в реализации и требуют меньше места, чем другие самобалансирующиеся деревья, поскольку информацию о балансе не нужно хранить в каждом узле.

Среднее время поиска расширенного дерева составляет O(log n) с использованием амортизированного анализа¹, что означает последовательность m операций для расширенного дерева с n узлам потребуется O(mlog n) времени². Дерево AVL имеет среднее время поиска O(log n) для любой отдельной операции. Поскольку наиболее часто используемые узлы находятся ближе к корню расширенного дерева, общее время выполнения последовательности операций теоретически намного быстрее.

«Расширенные деревья используются в Windows NT (в виртуальной памяти, сети и коде файловой системы), компиляторе gcc и библиотеке GNU C++, редакторе строк sed, сетевых маршрутизаторах Fore Systems, самой популярной реализации Unix malloc, загружаемых Linux модули ядра и во многих других программах». ³

Недостатки расширенного дерева

В отличие от дерева со сбалансированной высотой, расширенные деревья не могут гарантировать быстрое время поиска для одной операции. В то время как AVL может гарантировать время поиска в худшем случае O(log n), время поиска в худшем случае для одной операции в расширенном дереве — O(n). Если элементы вставлены по порядку, дерево может принять структуру связанного списка. Поэтому расширенное дерево не идеально подходит для одиночного поиска в реальном времени, поскольку оно оптимизировано для последовательности операций.

Когда доступ к элементам осуществляется с одинаковой частотой, преимущества расширения становятся устаревшими.

Кроме того, поскольку расширенные деревья изменяются после каждого поиска, их нельзя использовать в многопоточных средах с параллельным поиском.

Раскрыть

Расширение — это процесс, с помощью которого расширенное дерево перемещает заданный узел в корень дерева, используя серию поворотов. Эти вращения: Зиг, Заг, Зиг-Зиг, Заг-Заг, Зиг-Заг и Заг-Зиг.

Зиг и Заг

Зиг-образное вращение используется, если данный узел x является левым дочерним элементом своего родительского узла и является правым вращением. Поворот zag используется, когда данный узел y является правым дочерним элементом своего родительского узла и является поворотом влево. Требуется только одно вращение:

В следующем примере кода показано, как узлы меняются местами при вращении Zig (вправо):

// Zig at node x
void rightRotate(NodePtr x) {
    NodePtr y = x->left;
    x->left = y->right;
    if (y->right != nullptr) {
        y->right->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        this->root = y;
    } else if (x == x->parent->right) {
        x->parent->right = y;
    } else {
        x->parent->left = y;
    }
    y->right = x;
    x->parent = y;
}

В следующем примере кода показано, как узлы меняются местами при повороте Zag (влево):

// Zag at node x
void leftRotate(NodePtr x) {
    NodePtr y = x->right;
    x->right = y->left;
    if (y->left != nullptr) {
        y->left->parent = x;
    }
    y->parent = x->parent;
    if (x->parent == nullptr) {
        this->root = y;
    } else if (x == x->parent->left) {
        x->parent->left = y;
    } else {
        x->parent->right = y;
    }
    y->left = x;
    x->parent = y;
}

Если родитель текущего узла является корнем дерева. Произойдет зигзагообразное или загообразное вращение, чтобы переместить его в корень дерева:

if (!x->parent->parent) {
            if (x == x->parent->left) {
                // zig rotation
                rightRotate(x->parent);
            } else {
                // zag rotation
                leftRotate(x->parent);
            }
} 

Зиг-зиг и заг-заг

Зиг-зиг поворот используется, когда данный узел X является левым дочерним элементом своего родительского узлаP, а его родительский узел является левым дочерним элементом родительского узла Г. Как следует из названия, выполняются два зигзагообразных вращения в порядке сверху вниз; сначала вращаются родительский и прародительский узлы, затем вращаются родительский и текущий узлы.

Следующий код показывает случай, когда используется зиг-зиг:

else if (x == x->parent->left && x->parent == x->parent->parent->left) {
            // zig-zig rotation
            rightRotate(x->parent->parent);
            rightRotate(x->parent);
        } 

Загзагообразное вращение используется, когда данный узел X является правым дочерним элементом своего родительского узлаP, а его родительский узел является правым дочерним элементом родительского узла Г. Во-первых, между родительским и прародительским узлами происходит заг-образное вращение, затем происходит заг-вращение между родительским и текущим узлами:

Следующий код показывает случай, когда используется zag-zag:

else if (x == x->parent->right && x->parent == x->parent->parent->right) {
            // zag-zag rotation
            leftRotate(x->parent->parent);
            leftRotate(x->parent);
        } 

Зиг-Заг и Заг-Зиг

Зигзаг — это поворот вправо-влево. Это используется, если текущий узел X является левым дочерним элементом своего родительского узла P, а родительский узел является правым дочерним элементом родительского узла G. Сначала текущий узел и родительский узел поворачиваются зигзагообразным вращением, затем родительский узел и прародительский узел поворачиваются зигзагообразным вращением:

else if (x == x->parent->right && x->parent == x->parent->parent->left) {
            // zig-zag rotation
            leftRotate(x->parent);
            rightRotate(x->parent);
        } else {
            // zag-zig rotation
            rightRotate(x->parent);
            leftRotate(x->parent);
        }

void SplayTree::insert(int key) {
    // normal BST insert
    NodePtr node = new Node;
    node->parent = nullptr;
    node->left = nullptr;
    node->right = nullptr;
    node->data = key;
    NodePtr y = nullptr;
    NodePtr x = this->mRoot;

    while (x != nullptr) {
        y = x;
        if (node->data < x->data) {
            x = x->left;
        } else {
            x = x->right;
        }
    }

    // y is parent of x
    node->parent = y;
    if (y == nullptr) {
        mRoot = node;
    } else if (node->data < y->data) {
        y->left = node;
    } else {
        y->right = node;
    }

    // splay the node
    splay(node);
}

└──── denotes a right child and ├──── denotes a left child

Splay Tree Diagram:
└────20
     ├────7
     |    ├────3
     └────42
          ├────22
          |    └────39
          └────87
Pre-Order Traversal:
20 7 3 42 22 39 87

Splay Tree Diagram:
└────10
     ├────7
     |    ├────3
     └────20
          └────42
               ├────22
               |    └────39
               └────87
Pre-Order Traversal:
10 7 3 20 42 22 39 87

Splay Tree Diagram:
└────42
     ├────20
     |    ├────10
     |    |    ├────7
     |    |    |    ├────3
     |    └────22
     |         └────39
     └────87
Pre-Order Traversal:
42 20 10 7 3 22 39 87

//====================Part 1==================
void SplayTree::deleteNodeHelper(NodePtr node, int key) {
    NodePtr x = nullptr;
    NodePtr t, s;
    while (node != nullptr){
        if (node->data == key) {
            x = node;
        }

        if (node->data <= key) {
            node = node->right;
        } else {
            node = node->left;
        }
    }

    if (x == nullptr) {
        cout<<"Couldn't find key in the tree"<<endl;
        return;
    }
    splay(x);
//====================Part 2==================
    split(x, s, t); // split the tree
    if (s->left){ // remove x
        s->left->parent = nullptr;
    }
    //s->left is left subtree, t is right subtree
//====================Part 3==================
    mRoot = join(s->left, t);
    delete(s);
    s = nullptr;
}

Splay Tree Diagram:
└────20
     ├────10
     |    ├────7
     |    |    ├────3
     └────42
          ├────39
          └────87
Pre-Order Traversal:
20 10 7 3 42 39 87