Esta é a inserção BST eficiente?

Question

Implementei o método de inserção de árvore de pesquisa binária por conta própria apenas com base na lógica. Portanto, alguém pode verificar se o código está funcionando bem durante a inserção e a pesquisa (use seus próprios métodos de pesquisa, como inorder, preorder, postorder)?

E também descubra a complexidade de tempo do código.

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

    }
}

Editar: - Encontrei um problema ao inserir estes números: -

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

ele imprime assim (em ordem): - 10 11 80 70 12 13 90

Answer 1

Parece haver alguns problemas com seu código:

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

significa que dada uma árvore como:

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

E pedindo para inserir por exemplo 21, o algoritmo dado tentaria inseri-lo no filho esquerdo de 26. No entanto, este nó já foi tomado, portanto, seu algoritmo está falho. Eu sugeriria que você chame a inserção de cada nó recursivamente como:

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

Como cada nó é responsável por verificar se seus filhos estão vazios antes da inserção, esse problema não se repetirá.

Em termos de complexidade: você pode obter uma árvore como

1
 \
  2
   \
    3
     \
      ...
        \
         n

Onde inserir um valor maior do que n resultaria na passagem por n nós, portanto a complexidade do tempo é O (n).