Definición de árbol equilibrado

Me pregunto si alguien podría aclarar la definición de árbol equilibrado para mí. Tengo que "un árbol está equilibrado de cada subárbol está equilibrado y la altura de los dos subárboles difiere en la mayoría de uno.Definición de árbol equilibrado

Me disculpo si esta es una pregunta tonta, pero esta definición se aplica a cada nodo hasta las hojas de un árbol o solo a los subárboles izquierdo y derecho inmediatamente fuera de la raíz? Supongo que otra forma de preguntar esto sería preguntar si es posible que los nodos internos de un árbol estén desequilibrados y todo el árbol guardar el equilibrio?

Fuente

2011-11-04 Mark Soric

Solo quería agregar que estamos hablando de Comp. Definición científica de un subárbol: Un subárbol de un árbol T es un árbol que consiste en un nodo en T y todos sus descendientes en T. Para una definición matemática regular (un subgrafo de un árbol que es en sí mismo un árbol) no es verdad . –

no hay diferencia entre estas dos cosas. Piense en ello.

Tomemos una definición más simple, "un número positivo es incluso si es cero o que menos número dos es incluso " ¿Esto dice que 8 es incluso si 6 es par? ¿O dice esto 8 es incluso si 6, 4, 2 y 0 son pares?

No hay diferencia. Si dice 8 es incluso si 6 es par, también dice 6 es incluso si 4 es par. Y por lo tanto, también dice que 4 es incluso si 2 es par. Y así dice que 2 es incluso si 0 es par. Entonces, si dice que 8 es incluso si 6 es par, (indirectamente) dice 8 es incluso si 6, 4, 2 y 0 son par.

Pasa lo mismo aquí. Cualquier subárbol indirecto puede encontrarse mediante una cadena de subárboles directos. Por lo tanto, incluso si solo se aplica directamente a los subárboles directos, aún se aplica indirectamente a todos los subárboles (y por lo tanto a todos los nodos).

Fuente

2011-11-04 20:58:08

Digamos que el valor de la raíz es 15. A la derecha, tengo 16,17,18. A la izquierda tengo 14,13,12. ¿Es eso un árbol equilibrado? La altura de cada subárbol fuera del nodo está dentro de uno. Pero tome el primer nodo debajo de la raíz a la derecha, no tiene hijos abandonados pero la altura de sus hijos correctos es 2. Entonces ese nodo no está balanceado. ¿Es eso correcto? –

Correcto. Por lo tanto, el árbol no está equilibrado. –

Por lo tanto, para que un árbol se equilibre, cada nodo debe estar equilibrado. Belleza - Muchas gracias por su ayuda. –

La restricción generalmente se aplica recursivamente a cada subárbol. Es decir, el árbol sólo es equilibrada si:

alturas los subárboles izquierdo y derecho difieren como máximo en uno, y
El subárbol izquierdo es equilibrada, Y
El subárbol derecho es equilibrada

de acuerdo con esto, el siguiente árbol es equilibrada:

 A 
/ \ 
    B  C 
/ /\ 
D  E F 
    / 
    G

el siguiente es no equilibrado porque los subárboles de C difieren en 2 en su altura:

 A 
/ \ 
    B  C <-- difference = 2 
/ /
D  E 
    / 
    G

Dicho esto, la restricción específica de la primera punto depende del tipo de árbol. El que se menciona arriba es el típico para AVL trees.

Red-black trees, por ejemplo, imponen una restricción más suave.

Fuente

2013-02-05 16:30:30 comocomocomocomo

Existen varias formas de definir "Equilibrado". El objetivo principal es mantener las profundidades de todos los nodos en O(log(n)).

Me parece que la condición de balance que estaba hablando es para AVL árbol.
Aquí es la definición formal de la condición de equilibrio de AVL árbol:

Para cualquier nodo de AVL, la altura de su subárbol izquierdo difiere en como máximo 1 desde la altura de su subárbol derecho.

Siguiente pregunta ¿Qué es "height"?

El "altura" de un nodo en un árbol binario es la longitud de la trayectoria más larga desde dicho nodo a una hoja.

Hay un caso raro pero común:

gente define la altura de un árbol vacío para ser (-1).

Por ejemplo, hijo izquierdo de la raíz es null:

   A (Height = 2) 
     / \ 
(height =-1)  B (Height = 1) <-- Unbalanced because 1-(-1)=2 >1 
        \ 
        C (Height = 0)

Otros dos ejemplos para determinar:

Sí, A Balanced árbol Ejemplo:

 A (h=3) 
    / \ 
B(h=1)  C (h=2)   
/  / \ 
D (h=0) E(h=0) F (h=1) 
      /
       G (h=0)

No, No es un árbol balanceado Ejemplo:

 A (h=3) 
    / \ 
B(h=0)  C (h=2)  <-- Unbalanced: 2-0 =2 > 1 
     / \ 
     E(h=1) F (h=0) 
     / \ 
     H (h=0) G (h=0)

Fuente

2014-02-28 04:07:48 CherylG

Tenga en cuenta que esta definición permite subárboles no equilibrados de árboles equilibrados. (por ejemplo, extienda el ejemplo de árbol equilibrado anterior agregando un niño a D y otro a G) ¿Es esto intencional? – gen

El árbol equilibrado es un árbol cuya altura es del orden del registro (número de elementos en el árbol).

height = O(log(n)) 
O, as in asymptotic notation i.e. height should have same or lower asymptotic 
growth rate than log(n) 
n: number of elements in the tree

La definición dada "un árbol está equilibrado de cada sub-árbol es equilibrada y la altura de las dos sub-árboles difieren en como máximo un" es seguido por árboles AVL.

Dado que, los árboles AVL son equilibrados, pero no todos los árboles balanceados son árboles AVL, los árboles balanceados no tienen esta definición y los nodos internos pueden desequilibrarse en ellos. Sin embargo, los árboles AVL requieren que todos los nodos internos estén equilibrados.

Fuente

2015-06-08 05:57:31 div

el objetivo del árbol equilibrado es alcanzar la hoja en un mínimo de recorrido transversal (altura mínima). El grado del árbol es el número de ramas menos 1. Un árbol equilibrado puede no ser Binario.

Fuente

2017-03-22 20:08:44

Respuesta

Cuestiones relacionadas