Árbol cartesiano a partir del recorrido en orden | Árbol de segmentos

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}:  

  1. 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.
  2. Seleccione ‘arr[M]’ como el valor para el Node actual y cree un Node con este valor.
  3. Resuelva para el rango {L, M-1} y {M+1, R}.
  4. 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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *