miniatura|Uma sequência de números e a árvore cartesiana dela derivada.|alt=Consultar a legenda Na ciência da computação, uma árvore cartesiana é uma árvore binária derivada de uma sequência de números distintos. Para construir a árvore cartesiana, sua raiz é definida como o menor número da sequência, e suas subárvores esquerda e direita são construídas recursivamente a partir das subsequências anteriores e posteriores a esse número. Ela é definida de maneira única como uma heap mínimo cuja travessia simétrica (em ordem) retorna a sequência original.
As árvores cartesianas foram introduzidas por Vuillemin em 1980, no contexto de estruturas de dados geométricas para busca por intervalo. Elas também foram utilizadas na definição das estruturas de dados treap e árvore binária de busca aleatorizada para problemas de busca binária, em algoritmos de ordenação por comparação que apresentam desempenho eficiente em entradas quase ordenadas e como base para algoritmos de casamento de padrões. Uma árvore cartesiana para uma sequência pode ser construída em tempo linear.
Definição As árvores cartesianas são definidas usando árvores binárias, que são uma forma de árvore enraizada. Para construir a árvore cartesiana de uma determinada sequência de números distintos, define-se sua raiz como o menor número da sequência,Em algumas referências, a ordenação dos números é invertida, de modo que o nó raiz contém, em vez disso, o maior valor e a árvore possui a propriedade de heap máximo. e constroem-se recursivamente suas subárvores esquerda e direita a partir das subsequências anteriores e posteriores a esse número, respectivamente. Como caso-base, quando uma dessas subsequências está vazia, não há filho esquerdo ou direito.
Também é possível caracterizar a árvore cartesiana diretamente, em vez de recursivamente, usando suas propriedades de ordenação. Em qualquer árvore, a subárvore enraizada em um determinado nó consiste em todos os outros nós que podem alcançá-lo seguindo repetidamente os ponteiros para os pais. A árvore cartesiana de uma sequência de números distintos é definida pelas seguintes propriedades: A árvore cartesiana de uma sequência é uma árvore binária com um nó para cada número da sequência. Uma travessia simétrica (em ordem) da árvore resulta na sequência original. Equivalentemente, para cada nó, os números de sua subárvore esquerda aparecem antes dele na sequência, enquanto os números da subárvore direita aparecem depois. A árvore possui a propriedade de heap mínimo: o pai de qualquer nó que não seja a raiz possui um valor menor que o do próprio nó.
Essas duas definições são equivalentes: a árvore definida recursivamente conforme descrito acima é a única árvore que possui as propriedades listadas anteriormente. Se uma sequência de números contiver repetições, uma árvore cartesiana pode ser determinada para ela seguindo uma regra consistente de desempate antes de aplicar a construção acima. Por exemplo, o primeiro de dois elementos iguais pode ser tratado como sendo o menor dos dois.
História As árvores cartesianas foram introduzidas e nomeadas por , que as utilizou como exemplo da interação entre a combinatória geométrica e o projeto e a análise de estruturas de dados. Em particular, Vuillemin utilizou essas estruturas para analisar a complexidade de caso médio das operações de concatenação e divisão em árvores binárias de busca. O nome deriva do sistema de coordenadas cartesianas do plano: em uma versão dessa estrutura, assim como na aplicação de busca por intervalo bidimensional discutida abaixo, uma árvore cartesiana para um conjunto de pontos tem a ordem dos pontos ordenados por suas coordenadas como sua ordem de travessia simétrica, e possui a propriedade de heap de acordo com as coordenadas dos pontos. Vuillemin descreveu tanto essa versão geométrica da estrutura quanto a definição apresentada aqui, na qual uma árvore cartesiana é definida a partir de uma sequência. O uso de sequências em vez de coordenadas de pontos fornece um contexto mais geral, permitindo que a árvore cartesiana seja aplicada também a problemas não geométricos.
Construção eficiente Uma árvore cartesiana pode ser construída em tempo linear a partir de sua sequência de entrada. Um método consiste em processar os valores da sequência da esquerda para a direita, mantendo a árvore cartesiana dos nós já processados em uma estrutura que permita percorrer a árvore tanto para cima quanto para baixo. Para processar cada novo valor , começa-se no nó que representa o valor imediatamente anterior a na sequência e segue-se o caminho desse nó até a raiz da árvore, até encontrar um valor menor que . O nó torna-se o filho direito de , e o antigo filho direito de torna-se o novo filho esquerdo de . O tempo total desse procedimento é linear, pois o tempo gasto na busca pelo pai de cada novo nó pode ser amortizado pelo número de nós removidos do caminho mais à direita da árvore.
Um algoritmo alternativo de construção em tempo linear baseia-se no problema dos valores menores mais próximos de todos. Na sequência de entrada, define-se o vizinho esquerdo de um valor como o valor que ocorre antes de , é menor que e está mais próximo, em posição, de do que qualquer outro valor menor. O vizinho direito é definido de maneira simétrica. A sequência de vizinhos esquerdos pode ser encontrada por um algoritmo que mantém uma pilha contendo uma subsequência da entrada. Para cada novo valor da sequência, remove-se o elemento do topo da pilha repetidamente até que ela fique vazia ou seu elemento superior seja menor que ; então, é colocado na pilha. O vizinho esquerdo de é o elemento que está no topo no momento em que é colocado na pilha. Os vizinhos direitos podem ser encontrados aplicando o mesmo algoritmo de pilha à sequência invertida. O pai de na árvore cartesiana é o vizinho esquerdo ou o vizinho direito de , conforme o caso que exista e tenha o maior valor. Os vizinhos esquerdo e direito também podem ser construídos de maneira eficiente por algoritmos paralelos, tornando essa formulação útil para algoritmos paralelos eficientes de construção de árvores cartesianas.
Outro algoritmo de construção de árvores cartesianas em tempo linear baseia-se no método de divisão e conquista. O algoritmo constrói recursivamente a árvore em cada metade da entrada e, em seguida, combina as duas árvores. O processo de combinação envolve apenas as espinhas esquerda e direita dessas árvores: a espinha esquerda é o caminho obtido seguindo as arestas dos filhos esquerdos a partir da raiz até alcançar um nó sem filho esquerdo, e a espinha direita é definida de maneira simétrica. Assim como qualquer caminho em uma heap mínimo, ambas as espinhas têm seus valores em ordem crescente, do menor valor na raiz ao maior valor no final do caminho. Para combinar as duas árvores, aplica-se um algoritmo de intercalação à espinha direita da árvore esquerda e à espinha esquerda da árvore direita, substituindo esses dois caminhos nas duas árvores por um único caminho que contém os mesmos nós. No caminho combinado, o sucessor de cada nó da árvore esquerda na ordem de classificação é colocado como seu filho direito, e o sucessor de cada nó da árvore direita é colocado como seu filho esquerdo, na mesma posição anteriormente ocupada por seu sucessor na espinha. Os filhos esquerdos dos nós da árvore esquerda e os filhos direitos dos nós da árvore direita permanecem inalterados. O algoritmo pode ser paralelizado, pois, em cada nível da recursão, cada um dos dois subproblemas pode ser calculado em paralelo, e a operação de combinação também pode ser paralelizada de maneira eficiente.
Outro algoritmo de tempo linear, que utiliza uma representação da sequência de entrada por uma lista ligada, baseia-se na ligação por máximos locais: o algoritmo identifica repetidamente um elemento máximo local, isto é, um elemento maior que seus dois vizinhos (ou maior que seu único vizinho, caso seja o primeiro ou o último elemento da lista). Esse elemento é então removido da lista e ligado como filho direito de seu vizinho esquerdo, ou como filho esquerdo de seu vizinho direito, dependendo de qual dos dois vizinhos possui o maior valor, com os empates sendo resolvidos arbitrariamente. Esse processo pode ser implementado em uma única passagem da entrada da esquerda para a direita, e é fácil verificar que cada elemento pode receber no máximo um filho esquerdo e, no máximo, um filho direito, e que a árvore binária resultante é uma árvore cartesiana da sequência de entrada.
É possível manter a árvore cartesiana de uma entrada dinâmica, sujeita à inserção de elementos e à exclusão preguiçosa de elementos, em tempo amortizado logarítmico por operação. Nesse contexto, a exclusão preguiçosa significa que uma operação de exclusão é realizada marcando um elemento da árvore como excluído, mas sem removê-lo efetivamente da árvore. Quando o número de elementos marcados atinge uma fração constante do tamanho total da árvore, ela é reconstruída, mantendo apenas os elementos não marcados.
Aplicações Busca por intervalo e menores ancestrais comuns miniatura|Busca por intervalo bidimensional usando uma árvore cartesiana: o ponto inferior (vermelho na figura) dentro de uma região de três lados, com dois lados verticais e um lado horizontal (se a região não for vazia), pode ser encontrado como o menor ancestral comum dos pontos mais à esquerda e mais à direita (os pontos azuis na figura) dentro da faixa definida pelos limites verticais da região. Os pontos restantes da região de três lados podem ser encontrados dividindo-a por uma linha vertical que passa pelo ponto inferior e aplicando o procedimento recursivamente.|alt=Consultar a legenda As árvores cartesianas fazem parte de uma estrutura de dados eficiente para consultas do mínimo em intervalo. Uma entrada para esse tipo de consulta especifica uma subsequência contígua da sequência original; a saída da consulta deve ser o menor valor nessa subsequência. Em uma árvore cartesiana, esse valor mínimo pode ser encontrado no menor ancestral comum dos valores mais à esquerda e mais à direita da subsequência. Por exemplo, na subsequência (12, 10, 20, 15, 18) da sequência de exemplo, o menor valor da subsequência (10) forma o menor ancestral comum dos valores mais à esquerda e mais à direita (12 e 18). Como os menores ancestrais comuns podem ser encontrados em tempo constante por consulta, usando uma estrutura de dados que ocupa espaço linear e pode ser construída em tempo linear, os mesmos limites se aplicam ao problema de encontrar o mínimo em um intervalo.
inverteram essa relação entre os dois problemas de estrutura de dados ao mostrar que estruturas de dados para encontrar o mínimo em intervalos também podem ser utilizadas para encontrar menores ancestrais comuns. Sua estrutura de dados associa a cada nó da árvore sua distância até a raiz e constrói uma sequência dessas distâncias na ordem de uma volta de Euler da árvore (com cada aresta duplicada). Em seguida, constrói uma estrutura de dados para encontrar o mínimo em intervalos na sequência resultante. O menor ancestral comum de quaisquer dois vértices da árvore fornecida pode ser encontrado como a menor distância que aparece no intervalo entre as posições iniciais desses dois vértices na sequência. Bender e Farach-Colton também fornecem um método para encontrar o mínimo em intervalos que pode ser aplicado às sequências resultantes dessa transformação, que possuem a propriedade especial de que os valores adjacentes da sequência diferem em uma unidade. Como eles descrevem, para encontrar o mínimo em intervalos em sequências que não possuem essa forma, é possível usar árvores cartesianas para reduzir o problema de encontrar o mínimo em intervalos ao problema de encontrar menores ancestrais comuns e, em seguida, usar voltas de Euler para reduzir o problema de encontrar menores ancestrais comuns a um problema de encontrar o mínimo em intervalos nessa forma especial.