бесконечный цикл при обновлении высот для дерева двоичного поиска - PullRequest
Новая
       43

бесконечный цикл при обновлении высот для дерева двоичного поиска

0 голосов
/ 04 октября 2018

Я пытаюсь обновить высоту каждого узла в моем бинарном дереве поиска, когда добавляю новые узлы.Предполагая, что размещение каждой вставки правильное, почему я получаю бесконечный цикл при запуске: 

BinarySearchTree<Integer> bst = new BinarySearchTree<>((Integer x, Integer y) -> x < y);
int[] a = new int[] { 4,8 };
        for (Integer key : a)
          bst.insert(key);
        bst.updateHeights(bst.root.right);

Метод updateHeights: 

  public void updateHeights(Node k) {
      while(k.parent!=null) {
          k.parent.height=heightHelper(k.parent);
          updateHeights(k.parent);
      }       
  }

, а метод heightHelper:

 private int heightHelper(Node p){
          { 
                if (p == null) 
                    return 0; 
                else 
                { 

                    /* compute the depth of each subtree */
                    int lDepth = heightHelper(p.left); 
                    int rDepth = heightHelper(p.right); 

                    /* use the larger one */
                    if (lDepth > rDepth) 
                        return (lDepth + 1); 
                     else 
                        return (rDepth + 1); 
                }
          }

Получается правильная высота, но она никогда не вырывается из цикла while.Кроме того, я напечатал bst.root.parent, который имеет значение null, поэтому он должен выходить из строя после первого рекурсивного вызова, когда родительский узел корня передается в цикле while.Извините, если это глупая ошибка / вопрос.Заранее спасибо.

...