Hemos discutido la Introducción al Árbol Binario en el conjunto 1 y las Propiedades del Árbol Binario en el Conjunto 2 . En esta publicación, se analizan los tipos comunes de árboles binarios.
Los siguientes son tipos comunes de árboles binarios.
Árbol binario completo:
Un árbol binario es un árbol binario completo si cada Node tiene 0 o 2 hijos. Los siguientes son ejemplos de un árbol binario completo. También podemos decir que un árbol binario completo es un árbol binario en el que todos los Nodes excepto los Nodes hoja tienen dos hijos.
Un árbol binario completo es un tipo especial de árbol binario en el que cada Node padre/Node interno tiene dos o ningún hijo. También se conoce como árbol binario propio.
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 20
/ \
40 50
/ \
30 50
18
/ \
40 30
/ \
100 40
Árbol binario completo: –
Un Árbol Binario es un Árbol Binario Completo si todos los niveles están completamente llenos excepto posiblemente el último nivel y el último nivel tiene todas las claves como sea posible.
Un árbol binario completo es como un árbol binario completo, pero con dos diferencias principales:
- Cada nivel debe estar completamente lleno
- Todos los elementos de hoja deben inclinarse hacia la izquierda.
- El último elemento hoja podría no tener un hermano correcto, es decir, un árbol binario completo no tiene que ser un árbol binario completo.
Los siguientes son ejemplos de árboles binarios completos.
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 30
/ \ / \
40 50 100 40
/ \ /
8 7 9
Un ejemplo práctico de Árbol Binario Completo es Montón Binario .
Árbol binario perfecto: –
Un árbol binario es un árbol binario perfecto en el que todos los Nodes internos tienen dos hijos y todos los Nodes hoja están al mismo nivel.
Los siguientes son ejemplos de árboles binarios perfectos.
Un árbol binario perfecto es un tipo de árbol binario en el que cada Node interno tiene exactamente dos Nodes secundarios y todos los Nodes hoja están al mismo nivel.
18
/ \
15 30
/ \ / \
40 50 100 40
18
/ \
15 30
En un árbol binario perfecto, el número de Nodes hoja es el número de Nodes internos más 1
L = I + 1 Donde L = Número de Nodes hoja, I = Número de Nodes internos.
Un árbol binario perfecto de altura h (donde la altura del árbol binario es el número de aristas en el camino más largo desde el Node raíz hasta cualquier Node hoja del árbol, la altura del Node raíz es 0) tiene 2 h+1 – 1 Node.
Un ejemplo de un árbol binario perfecto son los antepasados de la familia. Mantener a una persona en la raíz, a los padres como hijos, a los padres de los padres como a sus hijos.
Árbol binario equilibrado:
un árbol binario está equilibrado si la altura del árbol es O (Log n), donde n es el número de Nodes. Por ejemplo, el árbol AVL mantiene la altura O(Log n) asegurándose de que la diferencia entre las alturas de los subárboles izquierdo y derecho sea como máximo 1. Los árboles rojo-negro mantienen la altura O(Log n) asegurándose de que el número de Nodes negros en todos los caminos de la raíz a la hoja es el mismo y no hay Nodes rojos adyacentes. Los árboles de búsqueda binaria equilibrada son buenos en cuanto a rendimiento, ya que proporcionan tiempo O (log n) para buscar, insertar y eliminar.
Ejemplo de árbol binario balanceado y no balanceado
Es un tipo de árbol binario en el que la diferencia entre la altura del subárbol izquierdo y derecho para cada Node es 0 o 1. En la figura anterior, el Node raíz que tiene un valor 0 está desequilibrado con una profundidad de 2 unidades. .
Un árbol degenerado (o patológico): –
Un árbol donde cada Node interno tiene un hijo. Dichos árboles tienen el mismo rendimiento que la lista enlazada.
Un árbol degenerado o patológico es el árbol que tiene un solo hijo, ya sea a la izquierda o a la derecha.
10
/
20
\
30
\
40
Árbol binario sesgado: –
Un árbol binario sesgado es un árbol patológico/degenerado en el que el árbol está dominado por los Nodes izquierdos o los Nodes derechos. Por lo tanto, hay dos tipos de árboles binarios sesgados: árboles binarios sesgados a la izquierda y árboles binarios sesgados a la derecha.
10 10
/ \
20 20
/ \
30 30
/ \
40 40
Left-Skewed Binary Tree Right-Skewed Binary Tree
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA