Splay-дерево. Вставка

МЕНЮ


Искусственный интеллект
Поиск
Регистрация на сайте
Помощь проекту
Архив новостей

ТЕМЫ


Новости ИИРазработка ИИВнедрение ИИРабота разума и сознаниеМодель мозгаРобототехника, БПЛАТрансгуманизмОбработка текстаТеория эволюцииДополненная реальностьЖелезоКиберугрозыНаучный мирИТ индустрияРазработка ПОТеория информацииМатематикаЦифровая экономика

Авторизация



RSS


RSS новости


Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: Splay-дерево. Поиск

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

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

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

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

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

4) В противном случае выделяем память для нового узла и сравниваем корневой ключ с k.

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

4.b) Если k больше корневого ключа, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла и делаем правый дочерний элемента корня равным 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] 

С++

#include <bits/stdc++.h> using namespace std;    // Узел АВЛ-дерева class node  {      public:     int key;      node *left, *right;  };     /* Вспомогательная функция, которая выделяет  новый узел с заданным key и left и right, указывающими в NULL. */ node* newNode(int key)  {      node* Node = new node();     Node->key = key;      Node->left = Node->right = NULL;      return (Node);  }     // Служебная функция для разворота поддерева с корнем y вправо. // Смотрите диаграмму, приведенную выше. 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;  }     // Эта функция поднимет ключ // в корень, если он присутствует в дереве.  // Если такой ключ отсутствует в дереве, она // поднимет в корень самый последний элемент, // к которому был осуществлен доступ. // Эта функция изменяет дерево // и возвращает новый корень (root). 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;             // Zig-Zig (Левый-левый)         if (root->left->key > key)          {              // Сначала рекурсивно поднимем              // ключ в качестве корня left-left             root->left->left = splay(root->left->left, key);                 // Первый разворот для root,               // второй разворот выполняется после else              root = rightRotate(root);          }          else if (root->left->key < key) // Zig-Zag (Left Right)          {              // Сначала рекурсивно поднимаем              // ключ в качестве кореня left-right             root->left->right = splay(root->left->right, key);                 // Выполняем первый разворот для root->left             if (root->left->right != NULL)                  root->left = leftRotate(root->left);          }             // Выполняем второй разворот для корня         return (root->left == NULL)? root: rightRotate(root);      }      else // Ключ находится в правом поддереве     {          // Ключа нет в дереве, мы закончили         if (root->right == NULL) return root;             // Zag-Zig (Правый-левый)         if (root->right->key > key)          {              // Поднять ключ в качестве кореня right-left             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)// Zag-Zag (Правый-правый)          {              // Поднимаем ключ в качестве корня               // right-right и выполняем первый разворот             root->right->right = splay(root->right->right, key);              root = leftRotate(root);          }             // Выполняем второй разворот для root         return (root->right == NULL)? root: leftRotate(root);      }  }     // Функция для вставки нового ключа k в splay-дерево с заданным корнем 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);         // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла     if (root->key > k)      {          newnode->right = root;          newnode->left = root->left;          root->left = NULL;      }         // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла     else     {          newnode->left = root;          newnode->right = root->right;          root->right = NULL;      }         return 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  ";      preOrder(root);      return 0;  }     // Этот код любезно предоставлен rathbhupendra 

C

// Код позаимствован c http://algs4.cs.princeton.edu/33balanced/SplayBST.java.html #include<stdio.h> #include<stdlib.h>    // Узел АВЛ-дерева struct node {     int key;     struct node *left, *right; };    /* Вспомогательная функция, которая создает  новый узел с заданным key и 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); }    // Служебная функция для разворота поддерева с корнем y вправо. // Смотрите диаграмму, приведенную выше. 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) {     // Базовые случаи: корень равен NULL или     // ключ находится в корне     if (root == NULL || root->key == key)         return root;        // Ключ лежит в левом поддереве     if (root->key > key)     {         // Ключа нет в дереве, мы закончили         if (root->left == NULL) return root;            // Zig-Zig (Левый-левый)         if (root->left->key > key)         {             // Сначала рекурсивно поднимем             // ключ как корень left-left             root->left->left = splay(root->left->left, key);                // Первый разворот для корня,              // второй разворот выполняется после else             root = rightRotate(root);         }         else if (root->left->key < key) // Zig-Zag (Левый-правый)         {             // Сначала рекурсивно поднимаем             // ключ как корень left-right             root->left->right = splay(root->left->right, key);                // Выполняем первый разворот для root->left             if (root->left->right != NULL)                 root->left = leftRotate(root->left);         }            // Выполняем второй разворот для корня         return (root->left == NULL)? root: rightRotate(root);     }     else // Ключ находится в правом поддереве     {         // Ключа нет в дереве, мы закончили         if (root->right == NULL) return root;            // Zag-Zig (Правый-левый)         if (root->right->key > key)         {             //Поднимаем ключ в качестве корня right-left             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)// Zag-Zag (Правый-правый)         {             // Поднимаем ключ в качестве корня              // right-right и выполняем первый разворот             root->right->right = splay(root->right->right, key);             root = leftRotate(root);         }            //Выполняем второй разворот для корня         return (root->right == NULL)? root: leftRotate(root);     } }    // Функция для вставки нового ключа k в splay-дерево с заданным корнем 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);        // Если корневой ключ больше, делаем корень правым дочерним элементом нового узла, копируем левый дочерний элемент корня в качестве левого дочернего элемента нового узла     if (root->key > k)     {         newnode->right = root;         newnode->left = root->left;         root->left = NULL;     }        // Если корневой ключ меньше, делаем корень левым дочерним элементом нового узла, копируем правый дочерний элемент корня в качестве правого дочернего элемента нового узла     else     {         newnode->left = root;         newnode->right = root->right;         root->right = NULL;     }        return 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  ");     preOrder(root);     return 0; } 

Вывод:

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

Узнать подробнее о курсе «Алгоритмы и структуры данных».Зарегистрироваться на открытый урок «Заповедники двоичных деревьев поиска».


Источник: habr.com

Комментарии: