En ciencias da computación, unha árbore binaria de busca (ABB), tamén chamada árbore binaria ordenada, é unha estrutura de datos de árbore binaria con raíz na que a chave de cada nó interno é maior que todas as chaves da súa subárbore esquerda e menor que as da súa subárbore dereita. A complexidade temporal das operacións é proporcional á altura da árbore.

As árbores binarias de busca permiten localizar, engadir e eliminar datos mediante comparacións: cada paso descarta unha das dúas subárbores. Non ten por que descartar a metade dos nós; o tempo é para unha altura , e só queda garantido como se a altura está así acoutada. Xurdiron na década de 1960 para o almacenamento eficiente de datos etiquetados, e o seu desenvolvemento atribúese a varios investigadores.

O rendemento dunha árbore binaria de busca depende da orde de inserción dos nós, pois insercións arbitrarias poden dexenerala; existen varias variantes con garantías no peor caso. As operacións básicas son a busca, o percorrido, a inserción e o borrado. As ABB con complexidades garantidas no peor caso funcionan mellor que un vector desordenado, que require busca linear.

A análise de complexidade da ABB depende do modelo das entradas. Se as chaves distintas se insiren nunha orde uniformemente aleatoria, as lonxitudes esperadas dos camiños de busca son ; isto non garante ese custo para unha secuencia arbitraria de insercións e borrados. No peor caso, a árbore pode dexenerar nunha lista ligada simple e unha operación custar . Para limitar o crecemento da altura con actualizacións arbitrarias, introducíronse variantes auto-equilibradas. As árbores AVL foron as primeiras árbores binarias de busca auto-equilibradas, inventadas en 1962 por Georgy Adelson-Velsky e Evgenii Landis. Tradución inglesa de Myron J. Ricci en Soviet Mathematics - Doklady, 3:1259–1263, 1962.

As árbores binarias de busca pódense empregar para implementar tipos de datos abstractos como os conxuntos dinámicos, as táboas de consulta e as colas de prioridade, e empréganse en algoritmos de ordenación como o tree sort.

Historia O algoritmo da árbore binaria de busca foi descuberto de forma independente por varios investigadores, entre eles P. F. Windley, Andrew Donald Booth, Andrew Colin e Thomas N. Hibbard. O algoritmo atribúese a Conway Berners-Lee e David Wheeler, que o usaron para almacenar datos etiquetados en cintas magnéticas en 1960. Un dos primeiros algoritmos de árbore binaria de busca, e un dos máis populares, é o de Hibbard.

A complexidade temporal dunha árbore binaria de busca medra coa altura se os nós se insiren nunha orde arbitraria; por iso se introduciron as árbores binarias de busca auto-equilibradas, que acoutan a altura a . As árbores AVL e as árbores rubinegras ofrecen esta garantía no peor caso; os treaps manteñen o equilibrio probabilisticamente.

Visión xeral Para chaves distintas, todas as da subárbore esquerda son menores ca a da raíz e todas as da dereita son maiores, segundo unha orde total. Se se admiten duplicados, cómpre fixar unha convención: a inserción que se mostra abaixo coloca as chaves iguais na subárbore dereita. Tamén se pode gardar un contador ou unha colección de valores nun único nó por chave.

As árbores binarias de busca tamén son eficaces na ordenación e na busca. Porén, a complexidade da busca depende da orde en que se insiren e borran os nós; no peor caso, operacións sucesivas poden dexenerar a árbore e formar unha estrutura semellante a unha lista ligada simple (ou «árbore desequilibrada»), coa mesma complexidade no peor caso ca unha lista ligada.

As árbores binarias de busca son tamén unha estrutura de datos fundamental na construción de estruturas de datos abstractas como os conxuntos, os multiconxuntos e as táboas asociativas.

Operacións Busca A busca dunha chave concreta nunha árbore binaria de busca pódese programar de forma recursiva ou iterativa.

A busca comeza examinando o nó raíz. Se a árbore é , a chave buscada non existe na árbore. En caso contrario, se a chave coincide coa da raíz, a busca ten éxito e devólvese o nó. Se a chave é menor que a da raíz, a busca continúa pola subárbore esquerda. Analogamente, se é maior, continúa pola subárbore dereita. O proceso repítese ata atopar a chave ou ata que a subárbore restante sexa .

Busca recursiva O pseudocódigo seguinte implementa o procedemento de busca da ABB mediante recursión. Recursive-Tree-Search(x, key) if x = NIL or key = x.key then return x if key < x.key then return Recursive-Tree-Search(x.left, key) else return Recursive-Tree-Search(x.right, key) end if

Busca iterativa A versión recursiva da busca pódese «desenrolar» nun bucle while. Na maioría das máquinas, a versión iterativa resulta máis eficiente. Iterative-Tree-Search(x, key) while x ≠ NIL and key ≠ x.key do if key < x.key then x := x.left else x := x.right end if repeat return x Como a busca pode avanzar ata algunha folla, a complexidade temporal da busca é , onde é a altura da árbore. Porén, o peor caso é , onde é o número total de nós. Se a ABB está equilibrada en altura, a altura é .

Sucesor e predecesor Nalgunhas operacións, dada un nó , é crucial atopar o seu sucesor ou predecesor. Supoñendo que todas as chaves dunha ABB son distintas, o sucesor dun nó é o nó coa menor chave maior que a chave de . O predecesor é o nó coa maior chave menor que a de . BST-Successor(x) if x.right ≠ NIL then return BST-Minimum(x.right) end if y := x.parent while y ≠ NIL and x = y.right do x := y y := y.parent repeat return y BST-Predecessor(x) if x.left ≠ NIL then return BST-Maximum(x.left) end if y := x.parent while y ≠ NIL and x = y.left do x := y y := y.parent repeat return y Operacións como atopar o nó cunha chave máxima ou mínima son críticas nalgúns casos. O pseudocódigo é o seguinte. BST-Maximum(x) while x.right ≠ NIL do x := x.right repeat return x BST-Minimum(x) while x.left ≠ NIL do x := x.left repeat return x

Inserción As operacións como a inserción e o borrado modifican dinamicamente a representación da ABB. Os novos nós insírense como nós folla. A continuación móstranse unha implementación iterativa da inserción. 1 BST-Insert(T, z) 2 y := NIL 3 x := T.root 4 while x ≠ NIL do 5 y := x 6 if z.key < x.key then 7 x := x.left 8 else 9 x := x.right 10 end if 11 repeat 12 z.parent := y 13 if y = NIL then 14 T.root := z 15 else if z.key < y.key then 16 y.left := z 17 else 18 y.right := z 19 end if

Borrado miniatura|400px|dereita|alt=Esquema dos tres casos de borrado dun nó nunha árbore binaria de busca.|Proceso de borrado dun nó nunha árbore binaria de busca. O borrado dun nó, por exemplo , da árbore binaria de busca ten tres casos: Se é un nó folla, substitúese por , como se mostra en (a). Se ten só un fillo, o fillo de ascende modificando o pai de para que apunte ao fillo, ocupando así a posición de , como se mostra en (b) e (c). Se ten fillos esquerdo e dereito, o sucesor en orde de , por exemplo , despraza a segundo dous casos: Se é o fillo dereito de , como se mostra en (d), despraza a e o fillo dereito de non cambia. Se está na subárbore dereita de pero non é o seu fillo dereito, como se mostra en (e), é substituído primeiro polo seu propio fillo dereito e despois despraza a da súa posición. Alternativamente, tamén se pode empregar o predecesor en orde.

O pseudocódigo seguinte implementa o borrado nunha árbore binaria de busca. 1 BST-Delete(BST, z) 2 if z.left = NIL then 3 Shift-Nodes(BST, z, z.right) 4 else if z.right = NIL then 5 Shift-Nodes(BST, z, z.left) 6 else 7 y := BST-Successor(z) 8 if y.parent ≠ z then 9 Shift-Nodes(BST, y, y.right) 10 y.right := z.right 11 y.right.parent := y 12 end if 13 Shift-Nodes(BST, z, y) 14 y.left := z.left 15 y.left.parent := y 16 end if 1 Shift-Nodes(BST, u, v) 2 if u.parent = NIL then 3 BST.root := v 4 else if u = u.parent.left then 5 u.parent.left := v 6 else 7 u.parent.right := v 8 end if 9 if v ≠ NIL then 10 v.parent := u.parent 11 end if

Percorrido Unha ABB pódese percorrer con tres algoritmos básicos: os percorridos en orde, en preorde e en postorde. Percorrido en orde: visítanse primeiro os nós da subárbore esquerda, despois a raíz e a subárbore dereita. Este percorrido visita todos os nós en orde de chave non decrecente. Percorrido en preorde: visítase primeiro a raíz e despois as subárbores esquerda e dereita. Percorrido en postorde: visítanse primeiro os nós da subárbore esquerda, despois a subárbore dereita e, finalmente, a raíz.

A continuación móstranse as implementacións recursivas dos percorridos. Inorder-Tree-Walk(x) if x ≠ NIL then Inorder-Tree-Walk(x.left) visitar o nó Inorder-Tree-Walk(x.right) end if Preorder-Tree-Walk(x) if x ≠ NIL then visitar o nó Preorder-Tree-Walk(x.left) Preorder-Tree-Walk(x.right) end if Postorder-Tree-Walk(x) if x ≠ NIL then Postorder-Tree-Walk(x.left) Postorder-Tree-Walk(x.right) visitar o nó end if

Árbores binarias de busca equilibradas Sen reequilibrado, as insercións ou os borrados poden dexenerar a árbore e acadar unha altura , co que o rendemento da busca se deteriora ao dunha busca linear. Manter a árbore equilibrada e a altura acoutada por é esencial. Isto pódese conseguir con mecanismos de «auto-equilibrado» durante as operacións de modificación.

Árbores equilibradas en altura Nas árbores AVL, as alturas das dúas subárbores de cada nó difiren como máximo nunha unidade. As rubinegras usan outra condición, baseada nas cores, que tamén garante unha altura . Estas garantías no peor caso deben distinguirse do equilibrio probabilístico dun treap.

Árbores equilibradas en peso Nunha árbore equilibrada en peso, o equilibrio contrólase mediante os tamaños das subárbores. As restricións habituais limitan as proporcións entre eses tamaños mediante parámetros constantes; non esixen que difiran como máximo nunha unidade.

Tipos Entre as árbores binarias de busca con equilibrio garantido están as AVL e as rubinegras. Os treaps ofrecen equilibrio probabilístico; as splay, cotas amortizadas sen garantir altura logarítmica. Os T-tree son estruturas de busca binarias con varios elementos por nó. As árbores B, 2-3 e 2-3-4 son estruturas relacionadas, pero non son binarias en xeral. Un montículo ordinario non satisfai a propiedade dunha árbore binaria de busca.

Exemplos de aplicacións Ordenación As árbores binarias de busca empréganse en algoritmos de ordenación como o tree sort, onde todos os elementos se insiren á vez e a árbore se percorre en orde.

Operacións de cola de prioridade As árbores binarias de busca empréganse para implementar colas de prioridade, usando a chave do nó como prioridade. Engadir elementos á cola segue a inserción normal dunha ABB, pero a operación de eliminación depende do tipo de cola de prioridade: Nunha cola de prioridade ascendente, a eliminación do elemento de menor prioridade faise percorrendo a ABB cara á esquerda. Nunha cola de prioridade descendente, a eliminación do elemento de maior prioridade faise percorrendo a ABB cara á dereita.

Notas

Véxase tamén Bibliografía

Outros artigos Árbore AVL Árbore binaria Árbore rubinegra Árbore de busca binaria óptima Árbore de busca ternaria

Ligazóns externas Árbores binarias de busca en Wikimedia Commons Ben Pfaff: An Introduction to Binary Search Trees and Balanced Trees (PDF, 1675 kB), 2004. Visualización dunha árbore binaria de busca

Categoría:Algoritmos Categoría:Programación