Рубрики

Treap | Набор 2 (реализация поиска, вставки и удаления)

Мы настоятельно рекомендуем ссылаться на набор 1 как обязательное условие этого поста.

Treap (рандомизированное дерево двоичного поиска)

В этом посте обсуждаются реализации поиска, вставки и удаления.

Поиск:
То же, что и стандартный поиск BST . Приоритет для поиска не учитывается.

// C функция для поиска заданного ключа в заданном BST

TreapNode* search(TreapNode* root, int key)

{

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

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

       return root;

      

    // Ключ больше ключа root

    if (root->key < key)

       return search(root->right, key);

   

    // Ключ меньше ключа root

    return search(root->left, key);

}

Вставить
1) Создайте новый узел с ключом, равным x, и значением, равным случайному значению.

2) Выполните стандартную вставку BST .

3) Вновь вставленный узел получает случайный приоритет, поэтому свойство Max-Heap может быть нарушено. Используйте вращения, чтобы убедиться, что приоритет вставленного узла следует за свойством max heap.

Во время вставки мы рекурсивно пересекаем всех предков вставленного узла.
a) Если новый узел вставлен в левое поддерево и корень левого поддерева имеет более высокий приоритет, выполните правое вращение.

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

/ * Рекурсивная реализация вставки в Treap * /

TreapNode* insert(TreapNode* root, int key)

{

    // Если root равен NULL, создать новый узел и вернуть его

    if (!root)

        return newNode(key);

  

    // Если ключ меньше чем root

    if (key <= root->key)

    {

        // Вставить в левое поддерево

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

  

        // Исправить свойство кучи, если оно нарушено

        if (root->left->priority > root->priority)

            root = rightRotate(root);

    }

    else  // Если ключ больше

    {

        // Вставить в правое поддерево

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

  

        // Исправить свойство кучи, если оно нарушено

        if (root->right->priority > root->priority)

            root = leftRotate(root);

    }

    return root;

}

Удалять:
Реализация удаления здесь немного отличается от шагов, обсужденных в предыдущем посте .
1) Если узел является листом, удалите его.
2) Если узел имеет один дочерний NULL, а другой — ненулевой, замените узел непустым дочерним.
3) Если узел имеет обоих потомков как ненулевые, найдите максимальное количество левого и правого потомков.
… .A) Если приоритет правого потомка больше, выполните левое вращение в узле
… .B) Если приоритет левого ребенка больше, выполните правое вращение в узле.

Идея шага 3 состоит в том, чтобы переместить узел вниз, чтобы в итоге мы получили вариант 1 или 2.

/ * Рекурсивная реализация Delete () * /

TreapNode* deleteNode(TreapNode* root, int key)

{

    // Базовый вариант

    if (root == NULL) return root;

  

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

    if (key < root->key)

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

    else if (key > root->key)

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

  

    // ЕСЛИ КЛЮЧ НА КОРНЕ

  

    // Если оставлено NULL

    else if (root->left == NULL)

    {

        TreapNode *temp = root->right;

        delete(root);

        root = temp;  // Сделать правильного ребенка корнем

    }

  

    // Если право равно NULL

    else if (root->right == NULL)

    {

        TreapNode *temp = root->left;

        delete(root);

        root = temp;  // Сделать левого ребенка корнем

    }

  

    // Если ksy в корне, а левый и правый не равны NULL

    else if (root->left->priority < root->right->priority)

    {

        root = leftRotate(root);

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

    }

    else

    {

        root = rightRotate(root);

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

    }

  

    return root;

}

Конкурсная программа для демонстрации всех операций

// C ++ программа для демостратирования поиска, вставки и удаления в Treap
#include <bits/stdc++.h>

using namespace std;

  
// Узел Трепа

struct TreapNode

{

    int key, priority;

    TreapNode *left, *right;

};

  
/ * T1, T2 и T3 являются поддеревьями дерева с корнем у

  (на левой стороне) или х (на правой стороне)

                у х

               // Правое вращение //

              х Т3 - - - - - - -> Т1 у

             / / <- - - - - - - / /

            T1 T2 левое вращение T2 T3 * /

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

    TreapNode *x = y->left,  *T2 = x->right;

  

    // Выполнить вращение

    x->right = y;

    y->left = T2;

  

    // Возвращаем новый корень

    return x;

}

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

    TreapNode *y = x->right, *T2 = y->left;

  

    // Выполнить вращение

    y->left = x;

    x->right = T2;

  

    // Возвращаем новый корень

    return y;

}

  
/ * Утилита для добавления нового ключа * /

TreapNode* newNode(int key)

{

    TreapNode* temp = new TreapNode;

    temp->key = key;

    temp->priority = rand()%100;

    temp->left = temp->right = NULL;

    return temp;

}

  
// C функция для поиска заданного ключа в заданном BST

TreapNode* search(TreapNode* root, int key)

{

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

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

       return root;

  

    // Ключ больше ключа root

    if (root->key < key)

       return search(root->right, key);

  

    // Ключ меньше ключа root

    return search(root->left, key);

}

  
/ * Рекурсивная реализация вставки в Treap * /

TreapNode* insert(TreapNode* root, int key)

{

    // Если root равен NULL, создать новый узел и вернуть его

    if (!root)

        return newNode(key);

  

    // Если ключ меньше чем root

    if (key <= root->key)

    {

        // Вставить в левое поддерево

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

  

        // Исправить свойство кучи, если оно нарушено

        if (root->left->priority > root->priority)

            root = rightRotate(root);

    }

    else  // Если ключ больше

    {

        // Вставить в правое поддерево

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

  

        // Исправить свойство кучи, если оно нарушено

        if (root->right->priority > root->priority)

            root = leftRotate(root);

    }

    return root;

}

  
/ * Рекурсивная реализация Delete () * /

TreapNode* deleteNode(TreapNode* root, int key)

{

    if (root == NULL)

        return root;

  

    if (key < root->key)

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

    else if (key > root->key)

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

  

    // ЕСЛИ КЛЮЧ НА КОРНЕ

  

    // Если оставлено NULL

    else if (root->left == NULL)

    {

        TreapNode *temp = root->right;

        delete(root);

        root = temp;  // Сделать правильного ребенка корнем

    }

  

    // Если право равно NULL

    else if (root->right == NULL)

    {

        TreapNode *temp = root->left;

        delete(root);

        root = temp;  // Сделать левого ребенка корнем

    }

  

    // Если ksy в корне, а левый и правый не равны NULL

    else if (root->left->priority < root->right->priority)

    {

        root = leftRotate(root);

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

    }

    else

    {

        root = rightRotate(root);

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

    }

  

    return root;

}

  
// Утилита для печати дерева

void inorder(TreapNode* root)

{

    if (root)

    {

        inorder(root->left);

        cout << "key: "<< root->key << " | priority: %d "

            << root->priority;

        if (root->left)

            cout << " | left child: " << root->left->key;

        if (root->right)

            cout << " | right child: " << root->right->key;

        cout << endl;

        inorder(root->right);

    }

}

  

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    srand(time(NULL));

  

    struct TreapNode *root = NULL;

    root = insert(root, 50);

    root = insert(root, 30);

    root = insert(root, 20);

    root = insert(root, 40);

    root = insert(root, 70);

    root = insert(root, 60);

    root = insert(root, 80);

  

    cout << "Inorder traversal of the given tree \n";

    inorder(root);

  

    cout << "\nDelete 20\n";

    root = deleteNode(root, 20);

    cout << "Inorder traversal of the modified tree \n";

    inorder(root);

  

    cout << "\nDelete 30\n";

    root = deleteNode(root, 30);

    cout << "Inorder traversal of the modified tree \n";

    inorder(root);

  

    cout << "\nDelete 50\n";

    root = deleteNode(root, 50);

    cout << "Inorder traversal of the modified tree \n";

    inorder(root);

  

    TreapNode *res = search(root, 50);

    (res == NULL)? cout << "\n50 Not Found ":

                   cout << "\n50 found";

  

    return 0;

}

Выход:

Inorder traversal of the given tree 
key: 20 | priority: %d 92 | right child: 50
key: 30 | priority: %d 48 | right child: 40
key: 40 | priority: %d 21
key: 50 | priority: %d 73 | left child: 30 | right child: 60
key: 60 | priority: %d 55 | right child: 70
key: 70 | priority: %d 50 | right child: 80
key: 80 | priority: %d 44

Delete 20
Inorder traversal of the modified tree 
key: 30 | priority: %d 48 | right child: 40
key: 40 | priority: %d 21
key: 50 | priority: %d 73 | left child: 30 | right child: 60
key: 60 | priority: %d 55 | right child: 70
key: 70 | priority: %d 50 | right child: 80
key: 80 | priority: %d 44

Delete 30
Inorder traversal of the modified tree 
key: 40 | priority: %d 21
key: 50 | priority: %d 73 | left child: 40 | right child: 60
key: 60 | priority: %d 55 | right child: 70
key: 70 | priority: %d 50 | right child: 80
key: 80 | priority: %d 44

Delete 50
Inorder traversal of the modified tree 
key: 40 | priority: %d 21
key: 60 | priority: %d 55 | left child: 40 | right child: 70
key: 70 | priority: %d 50 | right child: 80
key: 80 | priority: %d 44

50 Not Found 

Объяснение вышеприведенного вывода:

Every node is written as key(priority)

The above code constructs below tree
  20(92)
     \
     50(73)
     /     \
  30(48)   60(55) 
     \        \
  40(21)     70(50)
                \
                80(44)   


After deleteNode(20)
     50(73)
     /     \
  30(48)   60(55) 
     \        \
  40(21)     70(50)
                \
                80(44)   
 

After deleteNode(30)
     50(73)
     /     \
  40(21)   60(55) 
             \
             70(50)
               \
               80(44)   
 

After deleteNode(50)
     60(55)
     /     \
  40(21)  70(50)  
             \
            80(44)   

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

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

Treap | Набор 2 (реализация поиска, вставки и удаления)

0.00 (0%) 0 votes