Как найти предшественника узла в BST, где каждый узел имеет 3 атрибута -succ,left и right?

Question

Проблема из CLRS, 3ed.

12.3-5
Предположим, что вместо каждого узла x, хранящего атрибут xp, указывающий на родителя x, он сохраняет x.succ, указывая на преемника x. Дайте псевдокод для SEARCH,INSERT и DELETE в двоичном дереве поиска T, используя это представление. Эти процедуры должны работать за время O(h), где h - высота дерева T . (Подсказка: вы можете захотеть реализовать подпрограмму, которая возвращает родителя узла.)

Я знаю, как реализовать подпрограмму, которая возвращает родителя узла в O (H) времени.

Найти родителя узла x мы должны найти максимальный ключ M в поддереве с корнем в x первый. Затем мы идем вниз вправо от M.succ.left, Когда мы достигаем x, узел, с которым мы сталкиваемся раньше x является x родитель.

Смотрите код.

typedef struct TREE{
  struct TREE* left,right,succ;
}*BST;

PARENT(BST x)
{
  if(x==root) return NULL;
  BST max=TREE_MAXIMUM(x);
  BST parent=max->succ,t;
  if(parent) t=parent->left;
  else t=root;
  while(t!=x){parent=t;t=t->right;}
  return parent;
}

когда DELETEx, Succ из x Предшественник должен быть изменен, чтобы указать на x.succ, больше никогда x, Так что теперь возникает проблема - как найти предшественника x в O (ч) время?

Когда левое поддерево x непусто, это самый правый узел в x осталось поддерево. Однако, когда левое поддерево x пустой, предшественник x предка, чтобы найти, который вызывает O (H) раз PARENT, Для этого нужно время O (ч * ч)? Или мы должны искать вниз от корня?

Обратите внимание, что операция INSERT Также необходимо найти предшественника узла.

Возникает вопрос - а что, если все ключи имеют одинаковое значение? Тогда мы не можем найти x Предшественник, используя сравнение, для ключа a , который равен ключу x может появиться в x Левое поддерево или правое поддерево.

Answer 1

В случае, если левое поддерево x пустой, предшественник x это не просто его предок, это прямой родитель x, Так что вам нужно всего лишь один звонок на parent подпрограмма, делающая все время выполнения O(h)+O(h)=O(h),

PS
Даже если это не был прямой родитель, вам все равно не нужно звонить parent несколько раз, чтобы получить все предки, вы можете просто начать поиск x из корня дерева, как обычно, сохраняя все узлы вдоль пути к x в единственном обходе длины O(h), Все узлы, которые вы проходите при поиске xи только эти узлы, по определению, являются предками x,

Answer 2

Если ключи являются дискретными, у предшественника x есть ключ, который <= key(x)-1, верно? И если вы ищете в дереве ключ (x) -1, что произойдет? Не обязательно ли сталкиваться с pred (x) во время этого хода? Вы должны перепроверить меня на этом. И, конечно, недискретные ключи (например, с плавающей запятой) могут быть проблематичными (относительно -1).

Answer 3

Примечание: O(h) возможно только в том случае, если рут доступен напрямую (что и должно быть)

Немного изменив структуру данных.

typedef struct TREE{
 int key;
 struct TREE* left,right,succ;
}*BST;

Если левое поддерево не пустое, мы используем TREE_MAXIMUM, в противном случае мы ищем x в BST, начиная поиск с корня, и поддерживаем (в переменной target) последний (т. Е. Последний) узел, встреченный с правым потомком. В конце поиска цель - предшественник.

Предшественник функции

 BST PRE(BST x)
    {
      if(x->left!=NULL)
          return TREE_MAXIMUM(x->left);
      if(x== root)
          return NULL;
      BST goal = NULL, y = root;
      while(1)
      {
        if(x->key <= y->key)
            y=y->left;
        else
        {
            goal=y;
            y=y->right;
        }
        if(x==y)
        {
            return goal;
        }
      }      
    }