Árvore binária com costura

Árvore binária com costura, ou Árvore binária com fios é uma estrutura de dados derivada da Árvore de busca binária, em que os ponteiros nulos são aproveitados para armazenar o endereço do predecessor ou sucessor em in-ordem.

Uma Árvore de busca binária com $n$ elementos tem $n+1$ ponteiros. Para provar essa afirmação aplica-se indução sobre o número de elementos da árvore. Uma árvore com $k=1$ elemento tem dois ponteiros nulos. Adicionando um elemento em uma posição qualquer da árvore, um ponteiro deixa de ser nulo, porém surgem outros dois, pois novos elementos sempre são folhas. Assim a nova árvore tem $(k+1)-1+2=(k+1)+1$ ponteiros vazios.

Uma ligação de costura aproveita a memória desperdiçada por esses ponteiros para apontar para o predecessor (se o nodo não tiver filho esquerdo) ou para o sucessor (se o nodo não tiver filho direito). Isso torna o percusso in-ordem mais fácil de ser implementado e mais eficiente.

Estrutura

Com essa definição é necessário uma flag para destingüir que o ponteiro contém uma ligação de costura, ao invés de uma sub-árvore.

Um exemplo em C:

 struct nodo {
   int chave;
   struct nodo *esq;
   struct nodo *dir;
   int eFlag, dFlag;
 }

Exemplo de código da árvore:

 struct nodo *predecessor (struct nodo *p) {
   struct nodo *aux;
   if(p→eFlag == 1)
     aux = p→esq;
   else {
     aux = p→esq;
     while(aux→dFlag == 0) {
       aux = aux→dir;
     }
   }
   return aux;
 }

 struct nodo *sucessor(struct nodo *p) {
   struct nodo *aux;
   if(p→dFlag == 1)
     aux = p→dir;
   else {
     aux = p→dir;
     while(aux→eFlag == 0) {
        aux = aux→esq;
     }
   }
   return aux;
 }