Un árbol cartesiano es una estructura de datos de árbol creada a partir de un conjunto de datos que obedece a las siguientes invariantes estructurales:
- El árbol obedece a la propiedad del montón min (o max): cada Node es menor (o mayor) que sus hijos.
- Un recorrido en orden de los Nodes produce los valores en el mismo orden en que aparecen en la secuencia inicial.
Supongamos que tenemos una array de entrada: {5,10,40,30,28}. Entonces sería el árbol cartesiano max-heap.
Un árbol cartesiano min-heap de la array de entrada anterior será:
Nota:
- El árbol cartesiano no es un árbol de altura equilibrada.
- El árbol cartesiano de una secuencia de números distintos siempre es único.
El árbol cartesiano de una secuencia de números distintos siempre es único.
Probaremos esto usando inducción. Como caso base, el árbol vacío siempre es único. Para el caso inductivo, suponga que para todos los árboles que contienen n’ < n elementos, existe un único árbol cartesiano para cada secuencia de n’ Nodes. Ahora toma cualquier secuencia de n elementos. Debido a que un árbol cartesiano es un montón mínimo, el elemento más pequeño de la secuencia debe ser la raíz del árbol cartesiano. Debido a que un recorrido en orden de los elementos debe generar la secuencia de entrada, sabemos que todos los Nodes a la izquierda del elemento min deben estar en su subárbol izquierdo y de manera similar para los Nodes a la derecha. Dado que el subárbol izquierdo y derecho son ambos árboles cartesianos con como máximo n-1 elementos en ellos (ya que el elemento min está en la raíz), según la hipótesis de inducción, existe un árbol cartesiano único que podría ser el subárbol izquierdo o derecho. Como todas nuestras decisiones fueron forzadas,
¿Cómo construir el árbol cartesiano?
La solución AO (n 2 ) para la construcción del árbol cartesiano se analiza aquí (tenga en cuenta que el programa anterior aquí construye el «árbol binario especial» (que no es más que un árbol cartesiano
) Algoritmo AO (nlogn):
es posible construir un árbol cartesiano a partir de una secuencia de datos en tiempo O(NlogN) en promedio. Comenzando con el árbol vacío,
escanee la secuencia dada de izquierda a derecha agregando nuevos Nodes de la siguiente manera:
- Coloque el Node como el hijo derecho del Node más a la derecha.
- Explore hacia arriba desde el padre del Node hasta la raíz del árbol hasta que encuentre un Node cuyo valor sea mayor que el valor actual.
- Si se encuentra dicho Node, configure su hijo derecho para que sea el nuevo Node y configure el hijo izquierdo del nuevo Node para que sea el hijo derecho anterior.
- Si no se encuentra dicho Node, configure el nuevo hijo para que sea la raíz y configure el hijo izquierdo del nuevo Node para que sea el árbol anterior.
CPP
// A O(n) C++ program to construct cartesian tree
// from a given array
#include<bits/stdc++.h>
/* A binary tree node has data, pointer to left
child and a pointer to right child */
struct Node
{
int data;
Node *left, *right;
};
/* This function is here just to test buildTree() */
void printInorder (Node* node)
{
if (node == NULL)
return;
printInorder (node->left);
cout << node->data << " ";
printInorder (node->right);
}
// Recursively construct subtree under given root using
// leftChild[] and rightchild
Node * buildCartesianTreeUtil (int root, int arr[],
int parent[], int leftchild[], int rightchild[])
{
if (root == -1)
return NULL;
// Create a new node with root's data
Node *temp = new Node;
temp->data = arr[root] ;
// Recursively construct left and right subtrees
temp->left = buildCartesianTreeUtil( leftchild[root],
arr, parent, leftchild, rightchild );
temp->right = buildCartesianTreeUtil( rightchild[root],
arr, parent, leftchild, rightchild );
return temp ;
}
// A function to create the Cartesian Tree in O(N) time
Node * buildCartesianTree (int arr[], int n)
{
// Arrays to hold the index of parent, left-child,
// right-child of each number in the input array
int parent[n],leftchild[n],rightchild[n];
// Initialize all array values as -1
memset(parent, -1, sizeof(parent));
memset(leftchild, -1, sizeof(leftchild));
memset(rightchild, -1, sizeof(rightchild));
// 'root' and 'last' stores the index of the root and the
// last processed of the Cartesian Tree.
// Initially we take root of the Cartesian Tree as the
// first element of the input array. This can change
// according to the algorithm
int root = 0, last;
// Starting from the second element of the input array
// to the last on scan across the elements, adding them
// one at a time.
for (int i=1; i<=n-1; i++)
{
last = i-1;
rightchild[i] = -1;
// Scan upward from the node's parent up to
// the root of the tree until a node is found
// whose value is greater than the current one
// This is the same as Step 2 mentioned in the
// algorithm
while (arr[last] <= arr[i] && last != root)
last = parent[last];
// arr[i] is the largest element yet; make it
// new root
if (arr[last] <= arr[i])
{
parent[root] = i;
leftchild[i] = root;
root = i;
}
// Just insert it
else if (rightchild[last] == -1)
{
rightchild[last] = i;
parent[i] = last;
leftchild[i] = -1;
}
// Reconfigure links
else
{
parent[rightchild[last]] = i;
leftchild[i] = rightchild[last];
rightchild[last] = i;
parent[i] = last;
}
}
// Since the root of the Cartesian Tree has no
// parent, so we assign it -1
parent[root] = -1;
return (buildCartesianTreeUtil (root, arr, parent,
leftchild, rightchild));
}
/* Driver program to test above functions */
int main()
{
/* Assume that inorder traversal of following tree
is given
40
/ \
10 30
/ \
5 28 */
int arr[] = {5, 10, 40, 30, 28};
int n = sizeof(arr)/sizeof(arr[0]);
Node *root = buildCartesianTree(arr, n);
/* Let us test the built tree by printing Inorder
traversal */
printf("Inorder traversal of the constructed tree : \n");
printInorder(root);
return(0);
}
Java
// A O(n) Java program to construct cartesian tree
// from a given array
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class GFG
{
static class Node
{
int data;
Node left, right;
};
/* This function is here just to test buildTree() */
static void printInorder (Node node)
{
if (node == null)
return;
printInorder (node.left);
System.out.print(node.data + " ");
printInorder (node.right);
}
// Recursively construct subtree under given root using
// leftChild[] and rightchild
static Node buildCartesianTreeUtil (int root, int arr[],
int parent[], int leftchild[], int rightchild[])
{
if (root == -1)
return null;
// Create a new node with root's data
Node temp = new Node();
temp.data = arr[root] ;
// Recursively construct left and right subtrees
temp.left = buildCartesianTreeUtil( leftchild[root],
arr, parent, leftchild, rightchild );
temp.right = buildCartesianTreeUtil( rightchild[root],
arr, parent, leftchild, rightchild );
return temp ;
}
// A function to create the Cartesian Tree in O(N) time
static Node buildCartesianTree (int arr[], int n)
{
// Arrays to hold the index of parent, left-child,
// right-child of each number in the input array
int []parent = new int[n];
int []leftchild = new int[n];
int []rightchild = new int[n];
// Initialize all array values as -1
memset(parent, -1);
memset(leftchild, -1);
memset(rightchild, -1);
// 'root' and 'last' stores the index of the root and the
// last processed of the Cartesian Tree.
// Initially we take root of the Cartesian Tree as the
// first element of the input array. This can change
// according to the algorithm
int root = 0, last;
// Starting from the second element of the input array
// to the last on scan across the elements, adding them
// one at a time.
for (int i = 1; i <= n - 1; i++)
{
last = i - 1;
rightchild[i] = -1;
// Scan upward from the node's parent up to
// the root of the tree until a node is found
// whose value is greater than the current one
// This is the same as Step 2 mentioned in the
// algorithm
while (arr[last] <= arr[i] && last != root)
last = parent[last];
// arr[i] is the largest element yet; make it
// new root
if (arr[last] <= arr[i])
{
parent[root] = i;
leftchild[i] = root;
root = i;
}
// Just insert it
else if (rightchild[last] == -1)
{
rightchild[last] = i;
parent[i] = last;
leftchild[i] = -1;
}
// Reconfigure links
else
{
parent[rightchild[last]] = i;
leftchild[i] = rightchild[last];
rightchild[last] = i;
parent[i] = last;
}
}
// Since the root of the Cartesian Tree has no
// parent, so we assign it -1
parent[root] = -1;
return (buildCartesianTreeUtil (root, arr, parent,
leftchild, rightchild));
}
static void memset(int[] arr, int value)
{
for (int i = 0; i < arr.length; i++)
{
arr[i] = value;
}
}
/* Driver code */
public static void main(String[] args)
{
/* Assume that inorder traversal of following tree
is given
40
/ \
10 30
/ \
5 28 */
int arr[] = {5, 10, 40, 30, 28};
int n = arr.length;
Node root = buildCartesianTree(arr, n);
/* Let us test the built tree by printing Inorder
traversal */
System.out.printf("Inorder traversal of the" +
" constructed tree : \n");
printInorder(root);
}
}
// This code is contributed by PrinciRaj1992
C#
// A O(n) C# program to construct cartesian tree
// from a given array
/* A binary tree node has data, pointer to left
child and a pointer to right child */
using System;
class GFG
{
class Node
{
public int data;
public Node left, right;
};
/* This function is here just to test buildTree() */
static void printInorder (Node node)
{
if (node == null)
return;
printInorder (node.left);
Console.Write(node.data + " ");
printInorder (node.right);
}
// Recursively construct subtree under given root using
// leftChild[] and rightchild
static Node buildCartesianTreeUtil (int root, int []arr,
int []parent, int []leftchild, int []rightchild)
{
if (root == -1)
return null;
// Create a new node with root's data
Node temp = new Node();
temp.data = arr[root] ;
// Recursively construct left and right subtrees
temp.left = buildCartesianTreeUtil( leftchild[root],
arr, parent, leftchild, rightchild );
temp.right = buildCartesianTreeUtil( rightchild[root],
arr, parent, leftchild, rightchild );
return temp ;
}
// A function to create the Cartesian Tree in O(N) time
static Node buildCartesianTree (int []arr, int n)
{
// Arrays to hold the index of parent, left-child,
// right-child of each number in the input array
int []parent = new int[n];
int []leftchild = new int[n];
int []rightchild = new int[n];
// Initialize all array values as -1
memset(parent, -1);
memset(leftchild, -1);
memset(rightchild, -1);
// 'root' and 'last' stores the index of the root and the
// last processed of the Cartesian Tree.
// Initially we take root of the Cartesian Tree as the
// first element of the input array. This can change
// according to the algorithm
int root = 0, last;
// Starting from the second element of the input array
// to the last on scan across the elements, adding them
// one at a time.
for (int i = 1; i <= n - 1; i++)
{
last = i - 1;
rightchild[i] = -1;
// Scan upward from the node's parent up to
// the root of the tree until a node is found
// whose value is greater than the current one
// This is the same as Step 2 mentioned in the
// algorithm
while (arr[last] <= arr[i] && last != root)
last = parent[last];
// arr[i] is the largest element yet; make it
// new root
if (arr[last] <= arr[i])
{
parent[root] = i;
leftchild[i] = root;
root = i;
}
// Just insert it
else if (rightchild[last] == -1)
{
rightchild[last] = i;
parent[i] = last;
leftchild[i] = -1;
}
// Reconfigure links
else
{
parent[rightchild[last]] = i;
leftchild[i] = rightchild[last];
rightchild[last] = i;
parent[i] = last;
}
}
// Since the root of the Cartesian Tree has no
// parent, so we assign it -1
parent[root] = -1;
return (buildCartesianTreeUtil (root, arr, parent,
leftchild, rightchild));
}
static void memset(int[] arr, int value)
{
for (int i = 0; i < arr.Length; i++)
{
arr[i] = value;
}
}
/* Driver code */
public static void Main(String[] args)
{
/* Assume that inorder traversal of following tree
is given
40
/ \
10 30
/ \
5 28 */
int []arr = {5, 10, 40, 30, 28};
int n = arr.Length;
Node root = buildCartesianTree(arr, n);
/* Let us test the built tree by printing Inorder
traversal */
Console.Write("Inorder traversal of the" +
" constructed tree : \n");
printInorder(root);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// A O(n) Javascript program to construct cartesian tree
// from a given array
/* A binary tree node has data, pointer to left
child and a pointer to right child */
class Node
{
constructor(data)
{
this.data=data;
this.left=this.right=null;
}
}
/* This function is here just to test buildTree() */
function printInorder (node)
{
if (node == null)
return;
printInorder (node.left);
document.write(node.data + " ");
printInorder (node.right);
}
// Recursively construct subtree under given root using
// leftChild[] and rightchild
function buildCartesianTreeUtil(root,arr,parent,leftchild,rightchild)
{
if (root == -1)
return null;
// Create a new node with root's data
let temp = new Node();
temp.data = arr[root] ;
// Recursively construct left and right subtrees
temp.left = buildCartesianTreeUtil( leftchild[root],
arr, parent, leftchild, rightchild );
temp.right = buildCartesianTreeUtil( rightchild[root],
arr, parent, leftchild, rightchild );
return temp ;
}
// A function to create the Cartesian Tree in O(N) time
function buildCartesianTree (arr,n)
{
// Arrays to hold the index of parent, left-child,
// right-child of each number in the input array
let parent = new Array(n);
let leftchild = new Array(n);
let rightchild = new Array(n);
// Initialize all array values as -1
memset(parent, -1);
memset(leftchild, -1);
memset(rightchild, -1);
// 'root' and 'last' stores the index of the root and the
// last processed of the Cartesian Tree.
// Initially we take root of the Cartesian Tree as the
// first element of the input array. This can change
// according to the algorithm
let root = 0, last;
// Starting from the second element of the input array
// to the last on scan across the elements, adding them
// one at a time.
for (let i = 1; i <= n - 1; i++)
{
last = i - 1;
rightchild[i] = -1;
// Scan upward from the node's parent up to
// the root of the tree until a node is found
// whose value is greater than the current one
// This is the same as Step 2 mentioned in the
// algorithm
while (arr[last] <= arr[i] && last != root)
last = parent[last];
// arr[i] is the largest element yet; make it
// new root
if (arr[last] <= arr[i])
{
parent[root] = i;
leftchild[i] = root;
root = i;
}
// Just insert it
else if (rightchild[last] == -1)
{
rightchild[last] = i;
parent[i] = last;
leftchild[i] = -1;
}
// Reconfigure links
else
{
parent[rightchild[last]] = i;
leftchild[i] = rightchild[last];
rightchild[last] = i;
parent[i] = last;
}
}
// Since the root of the Cartesian Tree has no
// parent, so we assign it -1
parent[root] = -1;
return (buildCartesianTreeUtil (root, arr, parent,
leftchild, rightchild));
}
function memset(arr,value)
{
for (let i = 0; i < arr.length; i++)
{
arr[i] = value;
}
}
/* Driver code */
/* Assume that inorder traversal of following tree
is given
40
/ \
10 30
/ \
5 28 */
let arr = [5, 10, 40, 30, 28];
let n = arr.length;
let root = buildCartesianTree(arr, n);
/* Let us test the built tree by printing Inorder
traversal */
document.write("Inorder traversal of the" +
" constructed tree : <br>");
printInorder(root);
// This code is contributed by rag2127
</script>
Producción:
Inorder traversal of the constructed tree : 5 10 40 30 28
Complejidad del tiempo:
a primera vista, el código parece estar tomando un tiempo O (n 2 ) ya que hay dos bucles en buildCartesianTree(). Pero en realidad, se necesita un tiempo O (NlogN) en promedio y O (n ^ 2) para el recorrido ordenado por orden previa.
Espacio auxiliar:
declaramos una estructura para cada Node, así como tres arrays adicionales: hijo izquierdo [], hijo derecho [], padre [] para contener los índices de hijo izquierdo, hijo derecho, padre de cada valor en la array de entrada. Por lo tanto, el espacio extra total O(4*n) = O(n) .
Aplicación del Árbol Cartesiano
- Clasificación de árboles cartesianos
- Una consulta de rango mínimo en una secuencia es equivalente a una consulta del ancestro común más bajo en el árbol cartesiano de la secuencia. Por lo tanto, RMQ puede reducirse a LCA usando el árbol cartesiano de la secuencia.
- Treap, una estructura de árbol de búsqueda binaria equilibrada , es un árbol cartesiano de pares (clave, prioridad); se ordena en montón de acuerdo con los valores de prioridad, y un recorrido en orden proporciona las claves en orden ordenado.
- El árbol de sufijos de una string se puede construir a partir de la array de sufijos y la array de prefijos comunes más larga. El primer paso es calcular el árbol cartesiano de la array de prefijos comunes más larga.
Referencias:
http://wcipeg.com/wiki/Cartesian_tree
Este artículo es una contribución de Rachit Belwariar . Si le gusta GeeksforGeeks y le gustaría contribuir, también puede escribir un artículo y enviarlo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA