Рубрики

Декартово дерево

Декартово дерево — это древовидная структура данных, созданная из набора данных, который подчиняется следующим структурным инвариантам:

  1. Дерево подчиняется свойству кучи min (или max) — каждый узел меньше (или больше) своих дочерних узлов.
  2. Обход узлов по порядку дает значения в том же порядке, в котором они появляются в исходной последовательности.

Предположим, у нас есть входной массив — {5,10,40,30,28}. Тогда будет декартово дерево с максимальной кучей.

Декартово дерево с минимальной кучей указанного выше входного массива будет

Замечания:

  1. Декартово дерево не является сбалансированным по высоте деревом.
  2. Декартово дерево последовательности различных чисел всегда уникально.

Декартово дерево последовательности различных чисел всегда уникально.
Мы докажем это с помощью индукции. В качестве базового случая пустое дерево всегда уникально. Для индуктивного случая предположим, что для всех деревьев, содержащих n '<n элементов, существует уникальное декартово дерево для каждой последовательности из n' узлов. Теперь возьмем любую последовательность из n элементов. Поскольку декартово дерево — это минимальная куча, наименьший элемент последовательности должен быть корнем декартового дерева. Поскольку обход по порядку элементов должен давать входную последовательность, мы знаем, что все узлы слева от элемента min должны быть в его левом поддереве и аналогично для узлов справа. Так как левое и правое поддерево являются декартовыми деревьями с не более чем n-1 элементами в них (поскольку элемент min находится в корне), по предположению индукции существует уникальное декартово дерево, которое может быть левым или правым поддеревом. Поскольку все наши решения были вынужденными, мы получаем уникальное дерево, которое завершает индукцию.

Как построить декартово дерево?
Здесь обсуждается AO (n 2 ) решение для построения декартового дерева (обратите внимание, что приведенная выше программа здесь создает «специальное двоичное дерево» (которое является ничем иным, как декартовым деревом)

Алгоритм АО (нлогн):
Можно построить декартово дерево из последовательности данных в среднем за O (NlogN). Начиная с пустого дерева,

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

  1. Расположите узел как правый дочерний элемент самого правого узла.
  2. Сканирование вверх от родительского узла до корня дерева, пока не будет найден узел, значение которого больше текущего значения.
  3. Если такой узел найден, установите его правый дочерний узел в качестве нового узла и установите левый дочерний узел нового узла в качестве предыдущего правого дочернего узла.
  4. Если такой узел не найден, установите новый дочерний узел в качестве корневого и установите левый дочерний узел нового узла в качестве предыдущего дерева.

// AO (n) C ++ программа для построения декартового дерева
// из заданного массива
#include<bits/stdc++.h>

  
/ * Узел бинарного дерева имеет данные, указатель налево

   дочерний элемент и указатель на правый дочерний элемент * /

struct Node

{

    int data;

    Node *left, *right;

};

  
/ * Этот функционал здесь только для проверки buildTree () * /

void printInorder (Node* node)

{

    if (node == NULL)

        return;

    printInorder (node->left);

    cout << node->data << " ";

    printInorder (node->right);

}

  
// Рекурсивно построить поддерево под заданным корнем, используя
// leftChil [] и rightchild

Node * buildCartesianTreeUtil (int root, int arr[],

          int parent[], int leftchild[], int rightchild[])

{

    if (root == -1)

        return NULL;

  

    // Создать новый узел с данными root

    Node *temp = new Node;

    temp->data = arr[root] ;

  

    // Рекурсивное построение левого и правого поддеревьев

    temp->left = buildCartesianTreeUtil( leftchild[root],

                    arr, parent, leftchild, rightchild );

    temp->right = buildCartesianTreeUtil( rightchild[root],

                    arr, parent, leftchild, rightchild );

  

    return temp ;

}

  
// Функция для создания декартового дерева за O (N) время

Node * buildCartesianTree (int arr[], int n)

{

    // Массивы для хранения индекса parent, left-child,

    // правый потомок каждого числа во входном массиве

    int parent[n],leftchild[n],rightchild[n];

  

    // Инициализируем все значения массива как -1

    memset(parent, -1, sizeof(parent));

    memset(leftchild, -1, sizeof(leftchild));

    memset(rightchild, -1, sizeof(rightchild));

  

    // «корень» и «последний» хранит индекс корня и

    // последний обработан декартовым деревом.

    // Изначально мы укореняем декартово дерево как

    // первый элемент входного массива. Это может измениться

    // согласно алгоритму

    int root = 0, last;

  

    // Начиная со второго элемента входного массива

    // до последнего при сканировании по элементам, добавляя их

    // один за раз.

    for (int i=1; i<=n-1; i++)

    {

        last = i-1;

        rightchild[i] = -1;

  

        // Сканирование вверх от родительского узла до

        // корень дерева, пока не найден узел

        // значение которого больше текущего

        // Это то же самое, что Шаг 2, упомянутый в

        // алгоритм

        while (arr[last] <= arr[i] && last != root)

            last = parent[last];

  

        // arr [i] - самый большой элемент; сделай это

        // новый корень

        if (arr[last] <= arr[i])

        {

            parent[root] = i;

            leftchild[i] = root;

            root = i;

        }

  

        // Просто вставьте его

        else if (rightchild[last] == -1)

        {

            rightchild[last] = i;

            parent[i] = last;

            leftchild[i] = -1;

        }

  

        // Переконфигурируем ссылки

        else

        {

            parent[rightchild[last]] = i;

            leftchild[i] = rightchild[last];

            rightchild[last] = i;

            parent[i] = last;

        }

  

    }

  

    // Поскольку корень декартова дерева не имеет

    // родитель, поэтому мы присваиваем ему -1

    parent[root] = -1;

  

    return (buildCartesianTreeUtil (root, arr, parent,

                                    leftchild, rightchild));

}

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

int main()

{

    / * Предположим, что обход по порядку следующего дерева

       дано

         40

       / /

      10 30

     / /

    5 28 * /

  

    int arr[] = {5, 10, 40, 30, 28};

    int n = sizeof(arr)/sizeof(arr[0]);

  

    Node *root = buildCartesianTree(arr, n);

  

    / * Давайте проверим построенное дерево, напечатав Inorder

       обход * /

    printf("Inorder traversal of the constructed tree : \n");

    printInorder(root);

  

    return(0);

}

Выход:

Inorder traversal of the constructed tree :
5 10 40 30 28

Сложность времени:
На первый взгляд, кажется, что код занимает O (n 2 ) времени, так как в buildCartesianTree () есть два цикла. Но на самом деле, это занимает в среднем O (NlogN) времени и O (n ^ 2) для сортированного обхода предварительного заказа.

Вспомогательное пространство:
Мы объявляем структуру для каждого узла, а также три дополнительных массива — leftchild [], rightchild [], parent [] для хранения индексов left-child, right-child, parent каждого значения во входном массиве. Следовательно, общее O (4 * n) = O (n) дополнительное пространство.

Применение декартового дерева

  • Декартово дерево сортировка
  • Запрос минимального диапазона в последовательности эквивалентен запросу самого низкого общего предка в декартовом дереве последовательности. Следовательно, RMQ может быть уменьшен до LCA с использованием декартового дерева последовательности.
  • Treap, сбалансированная структура двоичного поиска , представляет собой декартово дерево пар (ключ, приоритет); это упорядочено в куче в соответствии со значениями приоритета, а обход по порядку дает ключи в отсортированном порядке.
  • Суффиксное дерево строки может быть построено из массива суффиксов и самого длинного массива общих префиксов. Первым шагом является вычисление декартового дерева самого длинного общего префиксного массива.

Ссылки:
http://wcipeg.com/wiki/Cartesian_tree

Эта статья предоставлена Rachit Belwariar . Если вам нравится GeeksforGeeks и вы хотите внести свой вклад, вы также можете написать статью и отправить ее по почте на contrib@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Декартово дерево

0.00 (0%) 0 votes