La Création D'Arbres Binaires

Si je construire un arbre de recherche binaire en ajoutant les valeurs suivantes dans l'ordre:

 10, 7, 16, 12, 5, 11, 2, 20, 1, 14

- Je obtenir un arbre de hauteur 5. Est-il une méthode (autre que l'essai et l'erreur) que je peux utiliser pour déterminer l'ordre des entiers qui permettrait de créer un arbre d'une hauteur de 4?

InformationsquelleAutor Tobi3 | 2012-05-11
  1. 5

    Je n'ai pas réfléchi complètement, mais un moyen d'obtenir un arbre de telle profondeur est de trier vos éléments avant de les insérer: c'est à dire le tri insertion de N éléments dans un arbre de recherche binaire va produire un arbre de profondeur N.

    Vous pourrait être en mesure de:

    1. Trier vos éléments
    2. Insérer un spécifique K=4 pour produire un arbre de profondeur K
    3. Insérer les éléments restants de telle manière que l'arbre n'a pas plus profondément.

    (Bien sûr, choisir les K éléments pour commencer et une stratégie pour insérer le reste des éléments est la partie la plus délicate -- mais peut-être que ce serait un début?)

    Modifier: je pense que la solution générale est possible, en supposant K est assez grand. Comment à ce sujet:

    1. Donné 10, 7, 16, 12, 5, 11, 2, 20, 1, 14
    2. Trier vos éléments: 1, 2, 5, 7, 10, 11, 12, 14, 16, 20
    3. Insérer le dernier K=4 éléments, puis le dernier K-1, K-2, et ainsi de suite, jusqu'à 1.

    Par exemple, après le tri et l'insertion de la dernière 4:

    12
  \
   14
     \
      16
        \
         20

    ...puis après l'insertion de la dernière 3:

      12
 / \
7    14
 \     \
  10    16
    \     \
     11    20

    ...puis après les 2 derniers:

        12
   / \
  7    14
 /\     \
2   10    16
 \    \     \
  5    11    20

    ...et enfin, après l'insertion du dernier élément:

          12
     / \
    7    14
   /\     \
  2   10    16
 /\    \     \
1   5    11    20

    ...vous êtes de gauche avec un TBS de hauteur K=4.

    Noter que cette approche ne fonctionne que lorsque K est assez grand, plus précisément, lorsque K(K+1)/2 >= N.

    • Où obtenez-vous le 18 dans l'arbre binaire?
    • désolé, faute de frappe. Devrait être corrigé maintenant.
    • Je ne pense pas que votre méthode fonctionne sur tous les cas. Disons que nous avons un arbre avec les numéros 1 à 7. Si nous utilisons vos méthode nous insérer 5,6,7 puis 3,4 puis 2, puis 1. Le résultat final est un arbre d'une hauteur de 4 à 5 le nœud racine. Cependant, il est possible d'organiser 7 nœuds comme parfaitement équilibré arbre binaire de hauteur 3, si nous utilisons 4 comme le nœud racine.
    • certes, cette approche ne fonctionne que lorsque K est assez grand. J'ai mis à jour la réponse.
    • Non, votre approche sera toujours un contre-exemple. L'exemple que j'ai donné de l'une parfaitement rempli tre avec 2^h - 1 éléments s'étend à tous les h et. Nous savons qu'il n'y a qu'une seule façon d'avoir cette densité d'arbres à rester en équilibre et, pour ce faire vous avez besoin de plus de la moitié des éléments à inclure le nœud racine et l' (densément emballé) sous-arbre droit. Si vous insérez dans l'ordre, comme vous l'avez suggéré, vous vous retrouvez avec seulement une colonne vertébrale, et il ne sera pas suffisant.
    • Je suis confus-ce que l'équilibrage avoir à faire avec l'OPs question? Pouvez-vous donner un exemple de N et de K, où K*(K+1)/2 >= N, où l'approche ci-dessus échoue à produire un TBS de hauteur K?
    • Je crois que je comprends maintenant: je pensais l'OP voulait un parfait équilibre de l'arbre (depuis le 4 est le plus petit en hauteur, nous pouvons obtenir avec ces éléments) alors que vous interprété comme si vous recevez K comme une entrée séparée qui peut être "sous-optimale"
    • ah, ok, fait sens. 🙂
    • si j'ai 7 éléments, je ne peux pas construire un BST à hauteur de 2 ou 3 par exemple?
    • vous pourriez certainement construire un BST à hauteur de 3 (pas la hauteur de 2) pour contenir 7 éléments, mais pas à l'aide de cette approche.
    • vous avez des liens vers quelques informations à ce sujet? par exemple je veux commander 2,5,6,11,17,18,22 Dans les hauteurs de 2,3,4,5,6 , quelle approche faut-il utiliser pour faire cela? Merci.

    InformationsquelleAutor Nate Kohl
  2. 5

    Oui, vous pouvez tout d'abord construire un parfait équilibre de l'arbre et vous pouvez alors la sortie de l'nœuds d'une manière qui a des nœuds parents d'être imprimé avant que leurs enfants.

    Pour créer un parfait équilibre de l'arbre, juste trier les nombres et l'utilisation récursive de divisions binaires pour construire un arbre.

    Par exemple, dans votre cas, nous permettrait de trier les nombres 

     1 2 5 7 10 11 12 14 16 20

    et ensuite construire un équilibre de l'arbre à partir d'eux (prendre le nombre moyen comme la racine et répéter ce processus de manière récursive)

                11
     5            14
 1     7       12    16
   2     10             20

    Nous pouvons maintenant utiliser une précommande de la traversée ou en largeur d'abord la traversée d'imprimer les nœuds dans l'ordre que vous voulez (tant que nous avons de sortie nœuds parents devant les enfants, nous allons être très bien).

    11 5 14 1 7 12 16 2 10 20
    InformationsquelleAutor hugomg
  3. 0
    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));
        }
    }
}
    InformationsquelleAutor iMobaio