Рубрики

Splay Tree | Комплект 2 (Вставка)

Рекомендуется ссылаться на следующий пост в качестве предпосылки этого поста.

Splay Tree | Комплект 1 (Поиск)

Как обсуждалось в предыдущем посте , Splay-дерево представляет собой самобалансирующуюся структуру данных, в которой последний доступный ключ всегда находится в корне. Операция вставки аналогична вставке в двоичное дерево поиска с дополнительными шагами, чтобы убедиться, что вновь вставленный ключ становится новым корнем.

Ниже приведены различные случаи вставки ключа k в Splay Tree.

1) Root имеет значение NULL: мы просто выделяем новый узел и возвращаем его как root.

2) Раскройте заданный ключ k. Если k уже присутствует, то он становится новым корнем. Если нет, то последний доступный конечный узел становится новым корнем.

3) Если ключ нового root совпадает с k, не делайте ничего, так как k уже присутствует.

4) В противном случае выделите память для нового узла и сравните ключ root с k.
……. 4.a) Если k меньше ключа root, сделать root правым дочерним узлом нового узла, скопировать левого дочернего элемента root как левого дочернего узла нового узла и сделать левого дочернего элемента root равным NULL.
……. 4.b) Если k больше ключа root, сделать root левым дочерним элементом нового узла, скопировать правого дочернего элемента root в качестве правого дочернего элемента нового узла и сделать правым дочерним элементом root значение NULL.

5) Вернуть новый узел как новый корень дерева.

Пример:

 
          100                  [20]                             25     
          /  \                   \                             /  \
        50   200                  50                          20   50 
       /          insert(25)     /  \        insert(25)           /  \  
      40          ======>      30   100      ========>           30  100    
     /          1. Splay(25)    \     \      2. insert 25         \    \
    30                          40    200                         40   200   
   /                                                          
 [20] 

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Узел дерева AVL

class node 

    public:

    int key; 

    node *left, *right; 

}; 

  
/ * Вспомогательная функция, которая выделяет
новый узел с данным ключом и

    NULL левый и правый указатели. * /

node* newNode(int key) 

    node* Node = new node();

    Node->key = key; 

    Node->left = Node->right = NULL; 

    return (Node); 

  
// Функция полезности справа
// вращаем поддерево с корнем у
// Смотрите диаграмму, приведенную выше.
node *rightRotate(node *x) 

    node *y = x->left; 

    x->left = y->right; 

    y->right = x; 

    return y; 

  
// Служебная функция слева
// вращаем поддерево с корнем x
// Смотрите диаграмму, приведенную выше.
node *leftRotate(node *x) 

    node *y = x->right; 

    x->right = y->left; 

    y->left = x; 

    return y; 

  
// Эта функция возвращает ключ в
// корень, если ключ присутствует в дереве.
// Если ключа нет, то это
// возвращает последний доступный элемент в
// корень. Эта функция изменяет
// дерево и возвращает новый корень

node *splay(node *root, int key) 

    // Базовые случаи: root равен NULL или

    // ключ присутствует в корне

    if (root == NULL || root->key == key) 

        return root; 

  

    // Ключ лежит в левом поддереве

    if (root->key > key) 

    

        // Ключ не в дереве, мы сделали

        if (root->left == NULL) return root; 

  

        // Зиг-Зиг (Слева Слева)

        if (root->left->key > key) 

        

            // Сначала рекурсивно вывести

            // ключ как корень слева-слева

            root->left->left = splay(root->left->left, key); 

  

            // сделать первый поворот для корня,

            // второй поворот выполняется после

            root = rightRotate(root); 

        

        else if (root->left->key < key) // зигзаг (слева направо)

        

            // Сначала рекурсивно вывести

            // ключ как корень слева направо

            root->left->right = splay(root->left->right, key); 

  

            // сделать первый поворот для корня-> влево

            if (root->left->right != NULL) 

                root->left = leftRotate(root->left); 

        

  

        // сделать второй поворот для корня

        return (root->left == NULL)? root: rightRotate(root); 

    

    else // Ключ лежит в правом поддереве

    

        // Ключ не в дереве, мы сделали

        if (root->right == NULL) return root; 

  

        // зигзаг (справа налево)

        if (root->right->key > key) 

        

            // Вывести ключ как корень справа налево

            root->right->left = splay(root->right->left, key); 

  

            // Делаем первый поворот для root-> right

            if (root->right->left != NULL) 

                root->right = rightRotate(root->right); 

        

        else if (root->right->key < key)// Заг-Заг (справа направо)

        

            // Получить ключ от корня

            // вправо-вправо и делаем первый поворот

            root->right->right = splay(root->right->right, key); 

            root = leftRotate(root); 

        

  

        // сделать второй поворот для корня

        return (root->right == NULL)? root: leftRotate(root); 

    

  
// Функция для вставки нового ключа k
// в дереве сплайнов с заданным корнем

node *insert(node *root, int k) 

    // Простой случай: если дерево пусто

    if (root == NULL) return newNode(k); 

  

    // Подвести ближайший листовой узел к корню

    root = splay(root, k); 

  

    // Если ключ уже присутствует, вернуть

    if (root->key == k) return root; 

  

    // В противном случае выделяем память для нового узла

    node *newnode = newNode(k); 

  

    // Если ключ root больше, make

    // root как правый потомок newnode

    // и копируем левого потомка root в newnode

    if (root->key > k) 

    

        newnode->right = root; 

        newnode->left = root->left; 

        root->left = NULL; 

    

  

    // Если ключ root меньше, сделать

    // root как левый потомок newnode

    // и копируем правого потомка root в newnode

    else

    

        newnode->left = root; 

        newnode->right = root->right; 

        root->right = NULL; 

    

  

    return newnode; // newnode становится новым корнем

  
// Утилита для печати
// предзаказ обхода дерева.
// Функция также печатает высоту каждого узла

void preOrder(node *root) 

    if (root != NULL) 

    

        cout<<root->key<<" "

        preOrder(root->left); 

        preOrder(root->right); 

    

  
/ * Код водителя * /

int main() 

    node *root = newNode(100); 

    root->left = newNode(50); 

    root->right = newNode(200); 

    root->left->left = newNode(40); 

    root->left->left->left = newNode(30); 

    root->left->left->left->left = newNode(20); 

    root = insert(root, 25); 

    cout<<"Preorder traversal of the modified Splay tree is \n"

    preOrder(root); 

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

// Этот код принят из http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html
#include<stdio.h>
#include<stdlib.h>

  
// Узел дерева AVL

struct node

{

    int key;

    struct node *left, *right;

};

  
/ * Вспомогательная функция, которая выделяет новый узел с данным ключом и

    NULL левый и правый указатели. * /

struct node* newNode(int key)

{

    struct node* node = (struct node*)malloc(sizeof(struct node));

    node->key   = key;

    node->left  = node->right  = NULL;

    return (node);

}

  
// Полезная функция для правого поворота поддерева с корнем у
// Смотрите диаграмму, приведенную выше.

struct node *rightRotate(struct node *x)

{

    struct node *y = x->left;

    x->left = y->right;

    y->right = x;

    return y;

}

  
// Вспомогательная функция левого поворота поддерева с корнем x
// Смотрите диаграмму, приведенную выше.

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    x->right = y->left;

    y->left = x;

    return y;

}

  
// Эта функция возвращает ключ в корень, если ключ присутствует в дереве.
// Если ключ отсутствует, то он возвращает последний доступный элемент в
// корень. Эта функция модифицирует дерево и возвращает новый корень

struct node *splay(struct node *root, int key)

{

    // Базовые случаи: root равен NULL или ключ присутствует в root

    if (root == NULL || root->key == key)

        return root;

  

    // Ключ лежит в левом поддереве

    if (root->key > key)

    {

        // Ключ не в дереве, мы сделали

        if (root->left == NULL) return root;

  

        // Зиг-Зиг (Слева Слева)

        if (root->left->key > key)

        {

            // Сначала рекурсивно приводим ключ как корень слева направо

            root->left->left = splay(root->left->left, key);

  

            // Делаем первый поворот для корня, второй поворот выполняется после else

            root = rightRotate(root);

        }

        else if (root->left->key < key) // зигзаг (слева направо)

        {

            // Сначала рекурсивно приводим ключ как корень слева направо

            root->left->right = splay(root->left->right, key);

  

            // сделать первый поворот для корня-> влево

            if (root->left->right != NULL)

                root->left = leftRotate(root->left);

        }

  

        // сделать второй поворот для корня

        return (root->left == NULL)? root: rightRotate(root);

    }

    else // Ключ лежит в правом поддереве

    {

        // Ключ не в дереве, мы сделали

        if (root->right == NULL) return root;

  

        // зигзаг (справа налево)

        if (root->right->key > key)

        {

            // Вывести ключ как корень справа налево

            root->right->left = splay(root->right->left, key);

  

            // Делаем первый поворот для root-> right

            if (root->right->left != NULL)

                root->right = rightRotate(root->right);

        }

        else if (root->right->key < key)// Заг-Заг (справа направо)

        {

            // Привести ключ как корень вправо-вправо и сделать первый поворот

            root->right->right = splay(root->right->right, key);

            root = leftRotate(root);

        }

  

        // сделать второй поворот для корня

        return (root->right == NULL)? root: leftRotate(root);

    }

}

  
// Функция для вставки нового ключа k в Splay Tree с заданным корнем

struct node *insert(struct node *root, int k)

{

    // Простой случай: если дерево пусто

    if (root == NULL) return newNode(k);

  

    // Подвести ближайший листовой узел к корню

    root = splay(root, k);

  

    // Если ключ уже присутствует, вернуть

    if (root->key == k) return root;

  

    // В противном случае выделяем память для нового узла

    struct node *newnode  = newNode(k);

  

    // Если ключ root больше, сделать root правым ребенком

    // newnode и скопировать левого потомка root в newnode

    if (root->key > k)

    {

        newnode->right = root;

        newnode->left = root->left;

        root->left = NULL;

    }

  

    // Если ключ root меньше, сделать root как левого потомка

    // newnode и копируем правого потомка root в newnode

    else

    {

        newnode->left = root;

        newnode->right = root->right;

        root->right = NULL;

    }

  

    return newnode; // newnode становится новым корнем

}

  
// Полезная функция для печати предзаказа обхода дерева.
// Функция также печатает высоту каждого узла

void preOrder(struct node *root)

{

    if (root != NULL)

    {

        printf("%d ", root->key);

        preOrder(root->left);

        preOrder(root->right);

    }

}

  
/ * Сушилка для проверки вышеуказанной функции * /

int main()

{

    struct node *root = newNode(100);

    root->left = newNode(50);

    root->right = newNode(200);

    root->left->left = newNode(40);

    root->left->left->left = newNode(30);

    root->left->left->left->left = newNode(20);

    root = insert(root, 25);

    printf("Preorder traversal of the modified Splay tree is \n");

    preOrder(root);

    return 0;

}


Выход:

Preorder traversal of the modified Splay tree is
25 20 50 30 40 100 200

Эта статья составлена Абхай Рати . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Splay Tree | Комплект 2 (Вставка)

0.00 (0%) 0 votes