Сложность печати времени BST методом преемника преемника

Question

У меня есть метод поиска следующего преемника inorder в дереве двоичного поиска (BST). Метод "inorderSuccessor" принимает любой узел BST в качестве входных данных и выводит следующий преемник inorder. Метод и класс дерева определены следующим образом:

class BSTInorderSuccessor{
  public static Node inorderSuccessor(Node node) {
    if (node.right != null) {
      return minValue(node.right);
    }
    Node parent = node.parent;
    while (parent != null && node == parent.right){
      node = parent;
      parent = parent.parent;
    }
    return parent;
  }
}

class TreeNode{
  int data;
  Node left;
  Node right;
  Node parent;
  public TreeNode(int data){
    this.data = data;
    this.left = null;
    this.right = null;
    this.parent = null;
  }
}

Предположим, что высота BST равна h, и в этой древовидной структуре есть n узлов. Я знаю, что временная сложность метода "inorderSuccessor" - O(h).

Мой вопрос: учитывая самый маленький узел BST. Когда я пишу метод для непрерывного вызова "inorderSuccessor" для печати всех узлов BST, какова общая сложность времени? Я думаю, что это O (N * H). Это верно?

Answer 1

Вы можете ограничить стоимость печати всего, всегда находя преемника inorder в O(nh), но на самом деле это не жесткая граница. Вы можете показать, что время выполнения на самом деле равно Θ(n), независимо от высоты дерева!

Один из способов увидеть это - посмотреть, сколько раз посещается каждое ребро дерева. Если вы проследите выполнение всех этих прохождений по порядку, вы обнаружите, что вы спускаетесь по каждому ребру ровно один раз и поднимаетесь по каждому ребру ровно один раз, а общая выполненная работа пропорциональна количеству посещений каждого ребра. Число ребер в дереве с n-узлами равно Θ(n), отсюда и ограничение времени выполнения.

Обратите внимание, что вы не можете сказать, что каждая отдельная операция займет время O(1). Это не правда. Что вы можете сказать, так это то, что в совокупности каждый из них занимает в среднем O (1) времени.