Привет, хабровчане. В преддверии старта курса Алгоритмы и структуры данных приглашаем будущих студентов и всех желающих на открытый урок по теме Заповедники двоичных деревьев поиска.
Также делимся традиционным полезным переводом.
Перед прочтением этой статьи настоятельно рекомендуется ознакомиться с первой частью: 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 \n"; 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 \n"); preOrder(root); return 0;}
Вывод:
Preorder traversal of the modified Splay tree is25 20 50 30 40 100 200
Узнать подробнее о курсе Алгоритмы и структуры данных.
Зарегистрироваться на открытый урок Заповедники двоичных деревьев поиска.
