Java двоичное дерево поиска - вставка реализации

Question

У меня возникла эта проблема с реализацией вставки двоичного дерева поиска. Теперь я попробовал это как с рекурсивным методом, так и с итеративным. Способ, который я получил до сих пор, «в порядке в лучшем случае», поскольку для дерева размером = 31609 и высоты дерева = 35 вставка занимает около 100 секунд, и предполагается, что WAAAAAAY опустится примерно на одну секунду. Может кто-нибудь, пожалуйста, дайте мне подсказку, что я могу делать неправильно?

Вот код того, что мне удалось сделать до сих пор (вставка без дубликатов):

void insert(int val){ 
    if(this.elem < val){ 
     if(this.right != null){ 
      this.right.insert(val); 
     } 
     else{ 
      nodes++; 
      this.right = new Node(val); 
     } 
    } 
    else if(this.elem > val){ 
     if(this.left != null){ 
      this.left.insert(val); 
     } 
     else{ 
      nodes++; 
      this.left = new Node(val); 

     } 
    } 
    else { 
     return; 
    } 
} 

Answer 1

, если вы используете функцию, определенную в строке 270 для вставки, долгое время на самом деле объясним.

посмотреть на этот кусок кода:

public void insert(int val) { 

     if (root == null) { 
      nodes++; 
      root = new Node(val); 
     } else if (!root.exists(val)) { 
      root.insert(val); 
     } 

    } 

это вызывает функция существует(), которая определяется следующим образом:

boolean exists(int val) { 
      return val == this.elem 
        || (val < this.elem ? (this.left != null && this.left.exists(val)) 
          : (this.right != null && this.right.exists(val))); 
     } 

и, как вы видите этот кусок кода, вы можете легко понять, что, возможно, каждый раз, когда вы вызываете эту функцию, ваш код рекурсивно пересекает все дерево! поэтому, если вы вставляете 100 тыс. раз, ваш код работает в O (n^2 * logn) в худшем случае, поэтому 100 секунд - это действительно хорошее время работы!

Я думаю, что вам нужно сделать, это изменить свою функцию существования().