Árvore cartesiana

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, 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: 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.

As árvores cartesianas foram introduzidas e nomeadas por Vuillemin (1980), 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 x {\displaystyle x} como sua ordem de travessia simétrica, e possui a propriedade de heap de acordo com as coordenadas y {\displaystyle y} 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.

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 a {\displaystyle a} , começa-se no nó que representa o valor imediatamente anterior a a {\displaystyle a} na sequência e segue-se o caminho desse nó até a raiz da árvore, até encontrar um valor b {\displaystyle b} menor que a {\displaystyle a} . O nó a {\displaystyle a} torna-se o filho direito de b {\displaystyle b} , e o antigo filho direito de b {\displaystyle b} torna-se o novo filho esquerdo de a {\displaystyle a} . O tempo total desse procedimento é linear, pois o tempo gasto na busca pelo pai b {\displaystyle b} de cada novo nó a {\displaystyle a} pode ser amortizado pelo número de nós removidos do caminho mais à direita da árvore.