Est-ce l'insertion BST efficace?

Question

J'ai implémenté la méthode d'insertion d'arbre de recherche binaire par moi-même en me basant simplement sur la logique. Alors, quelqu'un peut-il vérifier que le code fonctionne correctement lors de l'insertion et de la recherche (utilisez vos propres méthodes de recherche comme inorder, preorder, postorder)?

Et trouvez également la complexité temporelle du code.

public void insert(int data) {
    Node node = new Node(data);
    if (root == null) {
        root = node;
        size++;
    } else {
        Node n = root;
        if (data > n.data) {
            while (n.right != null) {
                n = n.right;
            }
            if (data < n.data) {
                while (n.left != null) {
                    n = n.left;
                }
                if (data != n.data) {
                    n.left = node;
                    size++;
                }
            } else {
                if (data != n.data) {
                    n.right = node;
                    size++;
                }
            }
        } else if (data < n.data) {
            while (n.left != null) {
                n = n.left;
            }
            if (data > n.data) {
                while (n.right != null) {
                    n = n.right;
                }
                if (data != n.data) {
                    n.right = node;
                    size++;
                }
            } else {
                if (data != n.data) {
                    n.left = node;
                    size++;
                }
            }
        }

    }
}

Edit: - J'ai trouvé un problème lorsque j'insère ces numéros: -

    bst.insert(10);
    bst.insert(11);
    bst.insert(90);
    bst.insert(13);
    bst.insert(12);
    bst.insert(70);
    bst.insert(80);

il imprime comme ceci (dans l'ordre): - 10 11 80 70 12 13 90

Answer 1

Il semble y avoir quelques problèmes avec votre code:

if (data > n.data) {
    while (n.right != null) {
                n = n.right;
                .
                .
                }
           }

signifie que, étant donné un arbre comme:

  10
 /  \
8    15
    / \
   12  23
         \
          26
         /
       20

Et en demandant d'insérer par exemple 21, l'algorithme donné tentera de l'insérer dans l'enfant gauche de 26. Cependant, ce nœud est déjà pris, donc votre algorithme est défectueux. Je vous suggère d'appeler l'insertion de chaque nœud de manière récursive comme:

// in class tree
public void insert(int data) {
    if (root == null) {
        root = new Node(data);
    } 
    else {
        root.insert(data);
    }
    size++;
}
//in class Node
public void insert(int data) {
    if(data>=this.data){
         if(right==null) right=new Node(data)
         else right.insert(data);
    }
    else{
         if(left==null) left=new Node(data)
         else left.insert(data);
    }
}

Étant donné que chaque nœud est responsable de vérifier si ses enfants sont vides avant l'insertion, ce problème ne se répétera pas.

En termes de complexité: vous pouvez obtenir un arbre comme

1
 \
  2
   \
    3
     \
      ...
        \
         n

Là où l'insertion d'une valeur supérieure à n entraînerait le passage sur n nœuds, la complexité temporelle est donc O (n).