Декартово дерево от обхода по порядку | Сегментное дерево
Опубликовано: 13 Января, 2022
При последовательном обходе декартова дерева задача состоит в том, чтобы построить из него все дерево.
Примеры:
Ввод: arr [] = {1, 5, 3}
Выход: 1 5 3
5
/
1 3
Ввод: arr [] = {3, 7, 4, 8}
Выход: 3 7 4 8
8
/
7
/
3 4
Рекомендуется: сначала попробуйте свой подход в {IDE}, прежде чем переходить к решению.
Подход: мы уже видели здесь алгоритм, который в среднем занимает O (NlogN) времени, но может достичь O (N 2 ) в худшем случае.
В этой статье мы увидим, как построить декартову систему для наихудшего времени работы O (Nlog (N)) . Для этого мы будем использовать дерево сегментов для ответа на запросы с максимальным диапазоном.
Ниже будет наш рекурсивный алгоритм для диапазона {L, R}:
- Найдите максимум в этом диапазоне {L, R}, используя запрос максимального диапазона на дереве сегментов. Скажем, «M» - это максимальное значение индекса в диапазоне.
- Возьмите 'arr [M]' как значение для текущего узла и создайте узел с этим значением.
- Найдите диапазон {L, M-1} и {M + 1, R}.
- Установите узел, возвращаемый {L, M-1}, как левый дочерний элемент текущего узла и {M + 1, R} как правый дочерний элемент.
Below is the implementation of the above approach:
C++
// C++ implementation of the approach#include <bits/stdc++.h>using namespace std; #define maxLen 30 // Node of the BSTstruct node { int data; node* left; node* right; node(int data) { left = NULL; right = NULL; this->data = data; }}; // Array to store segment treeint segtree[maxLen * 3]; // Function to create segment-tree to answer// range-max queryint buildTree(int l, int r, int i, int* arr){ // Base case if (l == r) { segtree[i] = l; return l; } // Maximum index in left range int l1 = buildTree(l, (l + r) / 2, 2 * i + 1, arr); // Maximum index in right range int r1 = buildTree((l + r) / 2 + 1, r, 2 * i + 2, arr); // If value at l1 > r1 if (arr[l1] > arr[r1]) segtree[i] = l1; // Else else segtree[i] = r1; // Returning the maximum in range return segtree[i];} // Function to answer range max queryint rangeMax(int l, int r, int rl, int rr, int i, int* arr){ // Base cases if (r < rl || l > rr) return -1; if (l >= rl and r <= rr) return segtree[i]; // Maximum in left range int l1 = rangeMax(l, (l + r) / 2, rl, rr, 2 * i + 1, arr); // Maximum in right range int r1 = rangeMax((l + r) / 2 + 1, r, rl, rr, 2 * i + 2, arr); // l1 = -1 means left range // was out-side required range if (l1 == -1) return r1; if (r1 == -1) return l1; // Returning the maximum // among two ranges if (arr[l1] > arr[r1]) return l1; else return r1;} // Function to print the inorder// traversal of the binary treevoid inorder(node* curr){ // Base case if (curr == NULL) return; // Traversing the left sub-tree inorder(curr->left); // Printing current node cout << curr->data << " "; // Traversing the right sub-tree inorder(curr->right);} // Function to build cartesian treenode* createCartesianTree(int l, int r, int* arr, int n){ // Base case if (r < l) return NULL; // Maximum in the range int m = rangeMax(0, n - 1, l, r, 0, arr); // Creating current node node* curr = new node(arr[m]); // Creating left sub-tree curr->left = createCartesianTree(l, m - 1, arr, n); // Creating right sub-tree curr->right = createCartesianTree(m + 1, r, arr, n); // Returning current node return curr;} // Driver codeint main(){ // In-order traversal of cartesian tree int arr[] = { 8, 11, 21, 100, 5, 70, 55 }; // Size of the array int n = sizeof(arr) / sizeof(int); // Building the segment tree buildTree(0, n - 1, 0, arr); // Building and printing cartesian tree inorder(createCartesianTree(0, n - 1, arr, n));} |
Java
// Java implementation of the approachimport java.util.*; class GFG{static int maxLen = 30; // Node of the BSTstatic class node{ int data; node left; node right; node(int data) { left = null; right = null; this.data = data; }}; // Array to store segment treestatic int segtree[] = new int[maxLen * 3]; // Function to create segment-tree to answer// range-max querystatic int buildTree(int l, int r, int i, int[] arr){ // Base case if (l == r) { segtree[i] = l; return l; } // Maximum index in left range int l1 = buildTree(l, (l + r) / 2, 2 * i + 1, arr); // Maximum index in right range int r1 = buildTree((l + r) / 2 + 1, r, 2 * i + 2, arr); // If value at l1 > r1 if (arr[l1] > arr[r1]) segtree[i] = l1; // Else else segtree[i] = r1; // Returning the maximum in range return segtree[i];} // Function to answer range max querystatic int rangeMax(int l, int r, int rl, int rr, int i, int[] arr){ // Base cases if (r < rl || l > rr) return -1; if (l >= rl && r <= rr) return segtree[i]; // Maximum in left range int l1 = rangeMax(l, (l + r) / 2, rl, rr, 2 * i + 1, arr); // Maximum in right range int r1 = rangeMax((l + r) / 2 + 1, r, rl, rr, 2 * i + 2, arr); // l1 = -1 means left range // was out-side required range if (l1 == -1) return r1; if (r1 == -1) return l1; // Returning the maximum // among two ranges if (arr[l1] > arr[r1]) return l1; else return r1;} // Function to print the inorder// traversal of the binary treestatic void inorder(node curr){ // Base case if (curr == null) return; // Traversing the left sub-tree inorder(curr.left); // Printing current node System.out.print(curr.data + " "); // Traversing the right sub-tree inorder(curr.right);} // Function to build cartesian treestatic node createCartesianTree(int l, int r, int[] arr, int n){ // Base case if (r < l) return null; // Maximum in the range int m = rangeMax(0, n - 1, l, r, 0, arr); // Creating current node node curr = new node(arr[m]); // Creating left sub-tree curr.left = createCartesianTree(l, m - 1, arr, n); // Creating right sub-tree curr.right = createCartesianTree(m + 1, r, arr, n); // Returning current node return curr;} // Driver codepublic static void main(String args[]){ // In-order traversal of cartesian tree int arr[] = { 8, 11, 21, 100, 5, 70, 55 }; // Size of the array int n = arr.length; // Building the segment tree buildTree(0, n - 1, 0, arr); // Building && printing cartesian tree inorder(createCartesianTree(0, n - 1, arr, n));}} // This code is contributed by Arnab Kundu |
Python3
# Python3 implementation of the approach # Node of a linked list class Node: def __init__(self, data = None, left = None, right = None ): self.data = data self.right = right self.left = left maxLen = 30 # Array to store segment treesegtree = [0]*(maxLen * 3) # Function to create segment-tree to answer# range-max querydef buildTree(l , r ,i , arr): global segtree global maxLen # Base case if (l == r) : segtree[i] = l return l # Maximum index in left range l1 = buildTree(l, int((l + r) / 2), 2 * i + 1, arr) # Maximum index in right range r1 = buildTree(int((l + r) / 2) + 1,r, 2 * i + 2, arr) # If value at l1 > r1 if (arr[l1] > arr[r1]): segtree[i] = l1 # Else else: segtree[i] = r1 # Returning the maximum in range return segtree[i] # Function to answer range max querydef rangeMax(l, r, rl, rr, i, arr): global segtree global maxLen # Base cases if (r < rl or l > rr): return -1 if (l >= rl and r <= rr): return segtree[i] # Maximum in left range l1 = rangeMax(l, int((l + r) / 2), rl, rr, 2 * i + 1, arr) # Maximum in right range r1 = rangeMax(int((l + r) / 2) + 1, r, rl, rr, 2 * i + 2, arr) # l1 = -1 means left range # was out-side required range if (l1 == -1): return r1 if (r1 == -1): return l1 # Returning the maximum # among two ranges if (arr[l1] > arr[r1]): return l1 else: return r1 # Function to print the inorder# traversal of the binary treedef inorder(curr): # Base caseРЕКОМЕНДУЕМЫЕ СТАТЬИ |