Dado un recorrido en orden de un árbol cartesiano, la tarea es construir todo el árbol a partir de él.
Ejemplos:
Input: arr[] = {1, 5, 3}
Output: 1 5 3
5
/ \
1 3
Input: arr[] = {3, 7, 4, 8}
Output: 3 7 4 8
8
/
7
/ \
3 4
Enfoque: Ya hemos visto un algoritmo aquí que toma tiempo O(NlogN) en promedio pero puede llegar a O(N 2 ) en el peor de los casos.
En este artículo, veremos cómo construir el tiempo de ejecución cartesiano en el peor de los casos de O(Nlog(N)) . Para esto, usaremos el árbol de segmentos para responder consultas de rango máximo.
A continuación se mostrará nuestro algoritmo recursivo en el rango {L, R}:
- Encuentre el máximo en este rango {L, R} usando la consulta range-max en el árbol de segmentos. Digamos que ‘M’ es el índice del máximo en el rango.
- Seleccione ‘arr[M]’ como el valor para el Node actual y cree un Node con este valor.
- Resuelva para el rango {L, M-1} y {M+1, R}.
- Establezca el Node devuelto por {L, M-1} como el hijo izquierdo del Node actual y {M+1, R} como el hijo derecho.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
#define maxLen 30
// Node of the BST
struct node {
int data;
node* left;
node* right;
node(int data)
{
left = NULL;
right = NULL;
this->data = data;
}
};
// Array to store segment tree
int segtree[maxLen * 4];
// Function to create segment-tree to answer
// range-max query
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 query
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 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 tree
void 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 tree
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 code
int 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 approach
import java.util.*;
class GFG
{
static int maxLen = 30;
// Node of the BST
static class node
{
int data;
node left;
node right;
node(int data)
{
left = null;
right = null;
this.data = data;
}
};
// Array to store segment tree
static int segtree[] = new int[maxLen * 4];
// Function to create segment-tree to answer
// range-max query
static 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 query
static 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 tree
static 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 tree
static 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 code
public 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 tree segtree = [0]*(maxLen * 4) # Function to create segment-tree to answer # range-max query def 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 query def 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 tree def inorder(curr): # Base case if (curr == None): return # Traversing the left sub-tree inorder(curr.left) # Printing current node print(curr.data, end= " ") # Traversing the right sub-tree inorder(curr.right) # Function to build cartesian tree def createCartesianTree(l , r , arr, n): # Base case if (r < l): return None # Maximum in the range m = rangeMax(0, n - 1, l, r, 0, arr) # Creating current node curr = 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 code # In-order traversal of cartesian tree arr = [ 8, 11, 21, 100, 5, 70, 55 ] # Size of the array n = len(arr) # 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
C#
// C# implementation of the approach
using System;
class GFG
{
static int maxLen = 30;
// Node of the BST
public class node
{
public int data;
public node left;
public node right;
public node(int data)
{
left = null;
right = null;
this.data = data;
}
};
// Array to store segment tree
static int []segtree = new int[maxLen * 4];
// Function to create segment-tree to answer
// range-max query
static 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 query
static 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 tree
static void inorder(node curr)
{
// Base case
if (curr == null)
return;
// Traversing the left sub-tree
inorder(curr.left);
// Printing current node
Console.Write(curr.data + " ");
// Traversing the right sub-tree
inorder(curr.right);
}
// Function to build cartesian tree
static 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 code
public static void Main()
{
// 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 AnkitRai01
Javascript
<script>
// Javascript implementation of the approach
var maxLen = 30;
// Node of the BST
class node
{
constructor(data)
{
this.data = data;
this.left = null;
this.right = null;
}
};
// Array to store segment tree
var segtree = Array(maxLen * 4).fill(0);
// Function to create segment-tree to answer
// range-max query
function buildTree(l, r, i, arr)
{
// Base case
if (l == r)
{
segtree[i] = l;
return l;
}
// Maximum index in left range
var l1 = buildTree(l, parseInt((l + r) / 2),
2 * i + 1, arr);
// Maximum index in right range
var r1 = buildTree(parseInt((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 query
function rangeMax(l, r, rl, rr, i, arr)
{
// Base cases
if (r < rl || l > rr)
return -1;
if (l >= rl && r <= rr)
return segtree[i];
// Maximum in left range
var l1 = rangeMax(l, parseInt((l + r) / 2), rl,
rr, 2 * i + 1, arr);
// Maximum in right range
var r1 = rangeMax(parseInt((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 tree
function inorder(curr)
{
// Base case
if (curr == null)
return;
// Traversing the left sub-tree
inorder(curr.left);
// Printing current node
document.write(curr.data + " ");
// Traversing the right sub-tree
inorder(curr.right);
}
// Function to build cartesian tree
function createCartesianTree(l, r, arr, n)
{
// Base case
if (r < l)
return null;
// Maximum in the range
var m = rangeMax(0, n - 1, l, r, 0, arr);
// Creating current node
var 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 code
// In-order traversal of cartesian tree
var arr = [ 8, 11, 21, 100, 5, 70, 55 ];
// Size of the array
var 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 noob2000
</script>
Producción:
8 11 21 100 5 70 55
Complejidad temporal: O(N+logN)
Espacio auxiliar : O(N).
Tema relacionado: Árbol de segmentos
Publicación traducida automáticamente
Artículo escrito por DivyanshuShekhar1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA