miniatura|alt=Árbore binaria etiquetada de tamaño 9 e altura 3, con raíz de valor 1. Está desequilibrada e non ordenada.|Árbore binaria etiquetada de tamaño 9 e altura 3, cunha raíz de valor 1. A árbore non está equilibrada nin ordenada.
En ciencias da computación, unha árbore binaria é unha estrutura de datos en árbore na que cada nó ten como máximo dous fillos, chamados fillo esquerdo e fillo dereito. É dicir, é unha árbore k-aria con . Unha definición recursiva en teoría de conxuntos describe unha árbore binaria como unha tripla , onde e son árbores binarias ou o conxunto baleiro e é un conxunto unitario que contén a raíz.
Desde a teoría de grafos, as árbores binarias así definidas son arborescencias. Por iso tamén se lles chama arborescencia bifurcante, termo que aparece nalgúns libros antigos de programación antes de que se impuxese a terminoloxía actual. Tamén se pode interpretar unha árbore binaria como un grafo non dirixido, no canto dun grafo dirixido, e entón é unha árbore ordenada con raíz. Algúns autores usan árbore binaria con raíz para salientar que a árbore ten raíz, aínda que, como se definiu arriba, unha árbore binaria sempre a ten.
En matemáticas, o que se entende por árbore binaria varía duns autores a outros. Algúns usan a definición habitual en ciencias da computación, mentres que outros definen que todo nó non folla ten exactamente dous fillos e tampouco os etiquetan necesariamente como esquerdo e dereito.
En informática, as árbores binarias empréganse de dúas maneiras moi distintas:
Primeiro, como medio de acceso aos nós a partir dun valor ou etiqueta asociados a cada nó. As árbores binarias etiquetadas deste xeito serven para implementar árbores binarias de busca e montículos binarios, e úsanse para a busca e a ordenación eficientes. A designación dos nós non raíz como fillos esquerdos ou dereitos, mesmo cando só hai un fillo, é relevante nalgunhas destas aplicacións, en particular nas árbores binarias de busca. Con todo, a disposición concreta dos nós na árbore non forma parte da información conceptual. Por exemplo, nunha árbore binaria de busca normal, a colocación dos nós depende case por completo da orde en que se engadiron, e pódese reorganizar (por exemplo, equilibrando) sen cambiar o significado. Segundo, como representación de datos cunha estrutura bifurcante relevante. Nestes casos, a disposición concreta dos nós baixo ou á esquerda ou dereita doutros forma parte da información (é dicir, cambiala cambiaría o significado). Exemplos habituais son a codificación de Huffman e os cladogramas. A división cotiá de documentos en capítulos, seccións e parágrafos é un exemplo análogo con árbores n-arias en lugar de binarias.
Definicións Definición recursiva Definición recursiva de árbore chea Unha descrición simple e informal dunha árbore binaria podería ser: unha árbore binaria ten un nó raíz, que ten 0 ou 2 nós fillos (que á súa vez poden ter os seus 0 ou 2 fillos, e así sucesivamente).
De forma máis formal: (caso base) Existe unha árbore chea formada por un único nó; (paso recursivo) Se T1 e T2 son árbores binarias cheas que non comparten ningún nó, e r é un nó que non pertence a T1 nin a T2, entón a tripla ordenada (r, T1, T2) é unha árbore binaria chea.
Esta definición implica dúas limitacións: unha árbore binaria chea contén polo menos un nó, e ningún nó pode ter un só fillo. Isto resólvese coa definición seguinte.
Definición recursiva de árbore estendida A definición de árbore estendida parte de que a árbore pode estar baleira. (caso base) Un conxunto baleiro de nós é unha árbore binaria estendida. (paso recursivo) Se T1 e T2 son árbores binarias estendidas que non comparten ningún nó, e r é un nó que non pertence a ningunha delas, entón a tripla ordenada (r, T1, T2) é unha árbore binaria estendida.
Para ser completas desde o punto de vista dos grafos, ambas as definicións deberían ampliarse cunha definición do conxunto de ramas correspondente. Informalmente, o conxunto de ramas descríbese como o conxunto de todos os pares ordenados de nós (r, s) onde é a raíz de calquera subárbore que aparece na definición e é a raíz de calquera das súas subárbores T1 e T2 (cando a subárbore respectiva non está baleira).
Outra forma de imaxinar esta construción (e de entender a terminoloxía) é considerar, no canto do conxunto baleiro, outro tipo de nó; por exemplo, nós cadrados se os normais son círculos.
Cos conceptos da teoría de grafos Unha árbore binaria é unha árbore con raíz que tamén é unha árbore ordenada (ou árbore plana) na que cada nó ten como máximo dous fillos. Unha árbore con raíz introduce de forma natural a noción de niveis (distancia á raíz); así, para cada nó pódese definir a noción de fillos como os nós conectados a el un nivel por debaixo. A ordenación destes fillos (por exemplo, debuxándoos nun plano) permite distinguir un fillo esquerdo dun fillo dereito. Pero isto aínda non distingue un nó con fillo esquerdo e sen dereito dun nó con fillo dereito e sen esquerdo.
A distinción necesaria pódese facer particionando as arestas: definindo a árbore binaria como a tripla (V, E1, E2), onde (V, E1 ∪ E2) é unha árbore con raíz (equivalentemente, unha arborescencia) e E1 ∩ E2 é baleiro, e esixindo ademais que, para todo j ∈ {1, 2}, cada nó teña como máximo un fillo por Ej. Unha forma máis informal de facer a distinción é dicir, citando a Encyclopedia of Mathematics, que «cada nó ten un fillo esquerdo, un fillo dereito, ningún ou ambos» e especificar que estas son «todas diferentes» como árbores binarias.Encyclopedia of Mathematics, «Binary tree». Tamén en papel: Michiel Hazewinkel (ed.), Encyclopaedia of Mathematics. Supplement I, Springer, 1997, páxina 124, ISBN 978-0-7923-4709-5.
Tipos de árbores binarias A terminoloxía das árbores non está ben normalizada e pode variar entre exemplos da bibliografía dispoñible. Unha árbore binaria con raíz ten un nó raíz e cada nó ten como máximo dous fillos. miniatura|alt=Árbore binaria chea de sete nós.|Unha árbore binaria chea. miniatura|alt=Árbore xenealóxica que se pode asignar a unha árbore binaria perfecta de catro niveis.|Unha táboa de devanceiros que se pode asignar a unha árbore binaria perfecta de catro niveis. Unha árbore binaria chea (ás veces chamada propia, plana ou estrita)Richard Stanley, Enumerative Combinatorics, volume 2, p. 36. é unha árbore na que cada nó ten 0 ou 2 fillos. Unha árbore binaria chea é, recursivamente: Un único vértice (un só nó como raíz). Unha árbore cuxa raíz ten dúas subárbores, ambas as dúas binarias cheas. Unha árbore binaria perfecta é unha árbore binaria na que todos os nós interiores teñen dous fillos e todas as follas teñen a mesma profundidade ou nivel (o nivel dun nó defínese como o número de arestas desde a raíz ata ese nó). Unha árbore binaria perfecta é unha árbore binaria chea. Unha árbore binaria completa é unha árbore binaria na que todos os niveis, agás quizais o último, están completamente cheos, e todos os nós do último nivel están o máis á esquerda posible. Pode ter entre 1 e 2h nós no último nivel h. Unha árbore perfecta é xa que logo sempre completa, pero unha árbore completa non sempre é perfecta. Algúns autores usan o termo completa para referirse a unha árbore binaria perfecta, e entón chaman a este tipo de árbore (co último nivel posiblemente non cheo) árbore binaria case completa. Unha árbore binaria completa pódese representar de forma eficiente cun vector. miniatura|alt=Árbore binaria completa que non é chea.|Unha árbore binaria completa (que non é chea). A árbore binaria completa infinita é unha árbore con niveis, onde para cada nivel d o número de nós existentes nese nivel é 2d. O número cardinal do conxunto de todos os niveis é (infinito numerábel). O cardinal do conxunto de todos os camiños (as «follas», por así dicir) é non numerábel, coa cardinalidade do continuo. Unha árbore binaria equilibrada é unha estrutura na que as subárbores esquerda e dereita de cada nó difiren en altura (o número de arestas desde o nó superior ata o máis afastado dunha subárbore) como máximo en 1.Aaron M. Tenenbaum et al., Data Structures Using C, Prentice Hall, 1990, ISBN 0-13-199746-7. Tamén se poden considerar árbores nas que ningunha folla está moito máis afastada da raíz ca outra.Paul E. Black (ed.), entrada «data structure» en Dictionary of Algorithms and Data Structures, NIST, 15 de decembro de 2004. Unha árbore dexenerada (ou patolóxica) é unha árbore na que cada nó pai ten un só fillo asociado. Isto significa que a árbore compórtase como unha lista ligada. Neste caso redúcese moito a vantaxe de usar unha árbore binaria, porque é esencialmente unha lista ligada na que a busca ten complexidade temporal O(n), mentres que a busca nunha árbore binaria de busca equilibrada ten complexidade O(log n). Unha árbore dexenerada tamén necesita máis memoria ca unha lista ligada, por ter dous punteiros por nó.
Propiedades das árbores binarias O número de nós nunha árbore binaria chea é polo menos e como máximo (o número de nós dunha árbore perfecta), onde é a altura. Unha árbore formada só pola raíz ten altura 0. O número mínimo de nós obtense engadindo só dous nós fillos por cada aumento de altura, de aí . O número máximo obtense enchendo por completo os nós de cada nivel, é dicir, unha árbore perfecta, onde (serie xeométrica). O número de follas nunha árbore binaria perfecta é (onde é o número de nós), porque e o número de follas é , de aí . En termos da altura , . Para calquera árbore binaria non baleira con follas e nós de grao 2 (nós interiores con dous fillos), . Se é o número de nós cun só fillo, entón e o número de arestas é ; restando estas igualdades obtense . Con nós, a altura mínima posible, contada en arestas, é . Unha árbore completa acada esa altura, sen ter que ser chea nin perfecta. A cota dedúcese de e de que a altura é enteira. A altura mínima dunha árbore binaria con follas é , porque e é un número enteiro. Nunha árbore binaria non baleira, se é o número total de nós e o número total de arestas, entón , porque cada nó necesita unha aresta agás a raíz. O número de ligazóns nulas (fillos ausentes dos nós) nunha árbore binaria de nós é . O número de nós interiores nunha árbore binaria completa de nós é .
Combinatoria En combinatoria considérase o problema de contar o número de árbores binarias cheas dun tamaño dado. Aquí as árbores non teñen valores nos nós e distínguense só pola súa estrutura; con todo, o fillo esquerdo e o dereito de cada nó distínguense. O tamaño da árbore tómase como o número n de nós interiores (os que teñen dous fillos); os demais nós son follas, e hai delas. O número de tales árbores de tamaño n é igual ao número de formas de pór parénteses a unha cadea de símbolos (as follas) separados por n operadores binarios (os nós interiores). Por exemplo, para hai que parentizar unha cadea como , o que é posible de cinco maneiras:
A correspondencia coas árbores binarias é evidente.
Hai unha única árbore binaria de tamaño 0 (unha soa folla), e calquera outra árbore caracterízase polo par dos seus fillos esquerdo e dereito; se estes teñen tamaños i e j, a árbore completa ten tamaño . Por tanto, o número de árbores binarias de tamaño n ten a descrición recursiva e . Así, é o número de Catalan de índice n.
As cadeas parentizadas anteriores non se deben confundir coas palabras de lingua de Dyck, que constan só de parénteses equilibradas. O seu número tamén é o número de Catalan . Por exemplo, hai cinco palabras de Dyck de lonxitude 6:
Estas palabras de Dyck non se corresponden coas árbores binarias do mesmo xeito; relaciónanse mediante unha bixección definida recursivamente.
Métodos de almacenamento As árbores binarias pódense construír de varias maneiras a partir de primitivas das linguaxes de programación.
Nós e referencias