¿Qué es un árbol binario desequilibrado y cuáles son sus usos?

Árbol que no impone restricciones en la diferencia de altura entre los nodos de hoja. bcz de esa altura de subárbol izquierda no coincide con el árbol derecho. se vuelve un árbol sesgado o desequilibrado.

Desventaja: el tiempo de búsqueda de elementos aumenta de olog (n) al peor caso de (n).

Uso: el árbol equilibrado sigue siendo un árbol de la bodega ds. y en promedio puede buscar un elemento en tiempo de registro, n número de elementos en el árbol.

La mayor ventaja del árbol es su estructura jerárquica, la forma en que mantiene la relación padre-hijo. esto hace que el árbol sea muy útil ds. aplicaciones como el análisis xml, el mantenimiento de la estructura de carpetas.

Para abordar el árbol desequilibrado, tenemos árboles autobalanceados como AVL, árbol de múltiples vías y árbol RB. estos más o menos aseguran la peor complejidad de tiempo de registro n tiempo. pero se requiere un esfuerzo adicional en términos de inserción y eliminación como rotaciones, manejo de desbordamiento.

Un árbol binario con [math] n [/ math] nodos (nodos de hoja y nodos internos, incluido el nodo raíz) y altura [math] h [/ math] se equilibra si se cumple lo siguiente: [math] 2 ^ {h -1} \ le n <2 ^ h [/ matemáticas]. De lo contrario, está desequilibrado. Por ejemplo, un árbol binario con altura 4 puede tener entre 8 y 15 nodos (entre 1 y 8 nodos de hoja) para equilibrar.

¿Son malos los árboles binarios desequilibrados? En la mayoría de los casos, sí, porque los árboles binarios balanceados son más compactos que los árboles binarios no balanceados y tienen una distancia máxima más pequeña desde la raíz hasta los nodos de las hojas. Pero depende de la aplicación, especialmente cómo se recorre desde el nodo raíz hasta los nodos hoja y qué decisión se toma al elegir si ir al subárbol izquierdo o derecho. Equilibrar un árbol binario puede cambiar su significado, por lo que el equilibrio no siempre es posible. En algunas aplicaciones, puede ser posible equilibrar un árbol binario, pero a menudo se difiere a un momento más conveniente en lugar de forzar el equilibrio en todo momento. Por ejemplo, el equilibrio puede realizarse después de las modificaciones [matemáticas] x [/ matemáticas] o una vez por intervalo de tiempo, en lugar de después de cada modificación.

Hay implementaciones de árbol binario que garantizan que el árbol esté equilibrado (o casi equilibrado) en todo momento, por ejemplo, árboles Rojo-Negros o árboles AVL.

Es un árbol que tiene una raíz y dos hijos secundarios izquierdo y derecho.

Se llamó desequilibrado porque tenemos un árbol de me gusta, por lo que en el peor de los casos tomaremos O (n) para obtener el nodo deseado al igual que la lista vinculada.

La mejor opción es equilibrar este árbol y usar el árbol AVL o lo que se llama árbol balanceado.