AVL Tree найти ближайший ключ

Question

Найдите строку: X, которая может существовать или не существовать в дереве AVL. Могу ли я получить псевдокод для получения X, если он существует, ИЛИ найти следующую наибольшую строку после X?

Я сделал код для преемника. Преемник находит следующий по величине узел.

protected BSTVertex successor(BSTVertex T) 
  {
    if (T.right != null)                       // this subtree has right subtree
      return findMin2(T.right);  // the successor is the minimum of right subtree
    else {
      BSTVertex par = T.parent;
      BSTVertex cur = T;
      // if par(ent) is not root and cur(rent) is its right children
      while ((par != null) && (cur == par.right)) {
        cur = par;                                         // continue moving up
        par = cur.parent;
      }
      return par == null ? null : par;           // this is the successor of T
    }
  }

Пример, если дерево состоит из чисел 1,2,3,4,7,9. Если я хочу найти 6, он должен вернуть мне 7, так как 6 не существует и следующее наибольшее значение 7

Answer 1

Вам нужен вариант search() функция, которая возвращает ближайший узел, следующий наибольший или последний листовой узел, который был проверен. Если это последний листовой узел, он не обязательно будет ближайшим. В вашем примере последний листовой узел может быть 2 или 9 для 6, а не обязательно 4 или 7.

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

/* returns the next biggest or null. If it's null, the first is the next biggest
\. */
BSTVertex searchOrNextBiggest(BSTVertex T, int key) {
    /* this.nextBiggest is the next biggest so far */
    if (T == null) return this.nextBiggest;
    else if (T.key == key) return T;

    /* is this the next biggest */
    if (T.key - key > 0 &&
        (this.nextBiggest == null ||
         T.key - key < this.nextBiggest.key - key))
        this.nextBiggest = T;

    if (T.key < key) return searchOrNextBiggest(T.left, key);
    else             return searchOrNextBiggest(T.right, key);
}