È questo l'inserimento BST efficiente?

Question

Ho implementato il metodo di inserimento dell'albero di ricerca binaria da solo basandomi sulla logica. Quindi, qualcuno può verificare che il codice funzioni correttamente durante l'inserimento e la ricerca (utilizzare i propri metodi di ricerca come inorder, preorder, postorder)?

E trova anche la complessità temporale del codice.

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++;
                }
            }
        }

    }
}

Modifica: - Ho riscontrato un problema quando inserisco questi numeri: -

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

stampa in questo modo (in ordine): - 10 11 80 70 12 13 90

Answer 1

Sembra che ci siano alcuni problemi con il tuo codice:

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

significa che dato un albero come:

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

E chiedendo di inserire ad esempio 21, l'algoritmo dato tenterebbe di inserirlo nel figlio sinistro di 26. Tuttavia questo nodo è già preso, quindi il tuo algoritmo è difettoso. Suggerirei di chiamare l'inserimento da ogni nodo in modo ricorsivo come:

// 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);
    }
}

Poiché ogni nodo è responsabile del controllo se i suoi figli sono vuoti prima dell'inserimento, questo problema non si ripeterà.

In termini di complessità: puoi ottenere un albero come

1
 \
  2
   \
    3
     \
      ...
        \
         n

Dove l'inserimento di un valore maggiore di n comporterebbe il passaggio su n nodi, quindi la complessità temporale è O (n).