á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 elementos tem ponteiros. Para provar essa afirmação aplica-se indução sobre o número de elementos da árvore. Uma árvore com 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 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.