¿Qué es un árbol de decisión binario en una estructura de datos?

(1) Si el subárbol izquierdo no está vacío, entonces el izquierdo. subárbol Los valores de todos los nodos en el subárbol derecho son menores que el valor de su nodo raíz;

(2) Si el subárbol derecho no está vacío, los valores de todos los nodos de la derecha el subárbol es mayor o igual que el valor de su nodo raíz;

(3) Los subárboles izquierdo y derecho también son árboles de clasificación binarios.

Datos extendidos:

Buscar

Pasos:

Árbol binario

Si el valor clave de la raíz nodo es igual a La palabra clave buscada fue exitosa.

De lo contrario, si es menor que el valor clave del nodo raíz, verifique recursivamente el subárbol izquierdo.

Si es mayor que el valor clave del nodo raíz, verifique recursivamente el subárbol derecho.

Si el subárbol está vacío, la búsqueda no tiene éxito.

Análisis de caso promedio (si se encuentran dos tipos con éxito):

Generalmente, sea P(n, I) la búsqueda promedio cuando el número de nodos en su subárbol izquierdo es I Longitud, el número de nodos como se muestra en la figura es n = 6, I = 3; luego p (n, I) = p (6, 3) = [1+(p(3)+1)* 3+( p( 2)+1)* 2]/6 =[1+(5).

Nota: P(3) y P(2) son las longitudes de búsqueda promedio de árboles de clasificación binaria de 3 y 2 nodos. En general, P(i) es la longitud de búsqueda promedio de un árbol de clasificación binaria con I nodos. Longitud promedio de búsqueda = suma de profundidades de cada nodo/número de puntos de resumen.

Enciclopedia Baidu: árbol de clasificación binaria