Si construyo un árbol binario de búsqueda añadiendo los valores siguientes en orden:Creación de árboles de búsqueda binaria
10, 7, 16, 12, 5, 11, 2, 20, 1, 14
me sale un árbol de altura 5. ¿Existe un método (que no sea de prueba y error) que pueda utilizar para determinar un orden de los enteros que crearía un árbol de altura 4?
no he pensado en esto por completo, pero una forma de conseguir un árbol de profundidad específica es para ordenar los elementos antes de la inserción de ellos: es decir, clasificando luego insertar N elementos en un árbol de búsqueda binaria producirá un árbol de profundidad N.
Usted podría será capaz de:
K=4 de ellos para producir un árbol de profundidad K(Por supuesto, la elección de qué K elementos para comenzar, y una estrategia para la inserción de los elementos restantes es la parte difícil? -, pero tal vez esto sería un buen comienzo)
Editar : Creo que es posible una solución general, suponiendo que K es lo suficientemente grande. ¿Qué tal esto:
10, 7, 16, 12, 5, 11, 2, 20, 1, 141, 2, 5, 7, 10, 11, 12, 14, 16, 20Por ejemplo, después de la clasificación y la inserción de la última 4:
12
\
14
\
16
\
20
... entonces después de insertar el último 3:
12
/\
7 14
\ \
10 16
\ \
11 20
... entonces después de la última 2:
12
/\
7 14
/\ \
2 10 16
\ \ \
5 11 20
... y finalmente, después de insertar el último elemento:
12
/\
7 14
/\ \
2 10 16
/\ \ \
1 5 11 20
... te queda una BST de altura K = 4.
Tenga en cuenta que este enfoque solo funcionará cuando K sea lo suficientemente grande, específicamente, cuando K(K+1)/2 >= N.
¿De dónde sacas? el 18 en el árbol binario? – Bytemain
@Chibox: lo siento, error. Debería ser arreglado ahora. –
No creo que su método funcione en todos los casos. Digamos que tenemos un árbol con los números del 1 al 7. Si usamos su método insertamos 5,6,7 luego 3,4 y luego 2, luego 1. El resultado final es un árbol de altura 4 con 5 como nodo raíz. Sin embargo, es posible organizar 7 nodos como un árbol binario perfectamente equilibrado con altura 3, si usamos 4 como nodo raíz. – hugomg
Sí, primero puede construir un árbol perfectamente equilibrado y luego puede generar los nodos de forma tal que los nodos primarios se impriman antes que sus hijos.
Para crear un árbol perfectamente equilibrado, solo ordene los números y luego use divisiones binarias recursivas para construir un árbol.
Por ejemplo, en su caso tendríamos ordenar los números
1 2 5 7 10 11 12 14 16 20
y luego construir un árbol de equilibrado de ellos (tomar el número del medio como la raíz y repetir este proceso de forma recursiva)
11
5 14
1 7 12 16
2 10 20
Ahora podemos usar un recorrido de preorden o un recorrido transversal ancho para imprimir los nodos en el orden que desee (siempre que generemos los nodos principales antes de los elementos secundarios).
11 5 14 1 7 12 16 2 10 20
public void testMakeBinarySearchTree() {
List<Integer> array = new ArrayList<>();
for (int i = 0; i < 10; i++) {
array.add(i+1);
}
Collections.shuffle(array);
Node root = new Node(array.get(5));
for (int value : array) {
binarySearchTreeInsertNode(root, value);
}
}
private void binarySearchTreeInsertNode(Node node, int value) {
int data = node.getData();
if (value > data) {
Node right = node.getRight();
if (right != null) {
binarySearchTreeInsertNode(right, value);
} else {
node.setRight(new Node(value));
}
} else if (value < data) {
Node left = node.getLeft();
if (left != null) {
binarySearchTreeInsertNode(left, value);
} else {
node.setLeft(new Node(value));
}
}
}
posible duplicado de [Equilibrio de una Binary Tree (AVL)] (http://stackoverflow.com/questions/133610/balancing-a-binary-tree-avl) – Flexo
Es necesario el [Equilibrio de Binary Tree] (http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree) –
No busco construir un árbol equilibrado como tal, más determino un ordenamiento de los enteros que obtendrían una altura de 4. – Tobi3