как я могу получить высоту красного черного дерева, а не черную высоту

Question

я пытаюсь получить высоту красного черного дерева, которое вставило в него файл из 3000+ слов, и это дает мне высоту = 1968. Я не знаю, была ли ошибка в части вставки или алгоритм вычисления высоты

функция для высоты

#define MAX(a,b) (((a)>(b))?(a):(b))
int height(Node* Root)
{
    int h = 0;

    if (Root != NULL) {
        if (Root == T_Nil)
            h = 1;
        else
        {
            int leftHeight  = height(Root->left);
            int rightHeight = height(Root->right);
            h = MAX(leftHeight, rightHeight) + 1;
        }
    }

    return h;
}

Имеет:

typedef struct Node {
 char word[128];
 char color;
 struct Node * left;
 struct Node *right;
 struct Node *parent; 
} Node;

struct Node T_Nil_Node;
Node * T_Nil = &T_Nil_Node;

функция вставки

 void redBlackInsert(Node** T, char word[128])
   {
   Node* z =  newNode(word);
   Node* y =  T_Nil;
   Node* x = *T;
   while (x != T_Nil)
   {
      y = x;
      if (strcmp(z->word,x->word)<0)
        x = x->left;
      else
        x = x->right;
   }

   z->parent = y;
   if (y == T_Nil)
     *T = z;
   else if (strcmp(z->word,y->word)<0)
      y->left  = z;
   else
      y->right = z;

   z->left  = T_Nil;
   z->right = T_Nil;
   z->color = RED;
   redBlackInsertFixup(T, z);
}

функция фиксирования

 void redBlackInsertFixup(Node** Root, Node* New)
 {
Node* temp;
while (New->parent->color == RED)
{
    if (New->parent == New->parent->parent->left)
    {
        temp = New->parent->parent->right;
        if (temp->color == RED)
        {
            New->parent->color = BLACK;
            temp->color = BLACK;
            New->parent->parent->color = RED;
            New = New->parent->parent;
        }
        else
        {
            if (New == New->parent->right)
            {
                New = New->parent;
                rotateLeft(Root, New);
            }
            New->parent->color = BLACK;
            New->parent->parent->color = RED;
            rotateRight(Root, New->parent->parent);
        }
    }
    else
    {
        temp = New->parent->parent->left;
        if (temp->color == RED)
        {
            New->parent->color = BLACK;
            New->color = BLACK;
            New->parent->parent->color = RED;
            New = New->parent->parent;
        }
        else
        {
            if (New == New->parent->left)
            {
                New = New->parent;
                rotateRight(Root, New);
            }
            New->parent->color = BLACK;
            New->parent->parent->color = RED;
            rotateLeft(Root, New->parent->parent);
        }
    }
}
Root[0]->color = BLACK;
 }

вращение влево

  void rotateLeft( Node** T, Node* x)
 {
  Node *y  = x->right;
x->right = y->left;
if (y->left != T_Nil)
    y->left->parent = x;
y->parent = x->parent;
if (x->parent == T_Nil)
    *T = y;
else if (x == x->parent->left)
    x->parent->left = y;
else
    x->parent->right = y;
y->left   = x;
x->parent = y;
 }

вращение вправо (я использую его для исправления)

void rotateRight(Node** T, Node* y)
{
Node *x  = y->left;
y->left  = x->right;
if (x->right != T_Nil)
    x->right->parent = y;
x->parent = y->parent;
if (y->parent == T_Nil)
    *T = x;
else if (y == y->parent->right)
    y->parent->right = x;
else
    y->parent->left  = x;
x->right  = y;
y->parent = x;
  }

Answer 1

Кажется, вы смешиваете NULL и сторожевой узел NIL в вашей функции height.Либо вы используете NULL для обозначения «без детей», либо вы используете сторожевой объект NIL.И то, и другое одновременно кажется неправильным.

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

Вот как я мог бы ожидать, что код будет ...

Используя sentinel NIL (что, кажется, вы хотите сделать)

int height(Node* Root)
{
    assert(Root != NULL);          // NULL is never allowed
    if (Root == T_Nil) return 0;   // No data here so return 0

    int leftHeight  = height(Root->left);
    int rightHeight = height(Root->right);
    int h = MAX(leftHeight, rightHeight) + 1;
    return h;
}

Использование NULL (что, по-видимому, не нужно делать)

int height(Node* Root)
{
    if (Root == NULL) return 0;   // No data here so return 0

    int leftHeight  = height(Root->left);
    int rightHeight = height(Root->right);
    int h = MAX(leftHeight, rightHeight) + 1;
    return h;
}

Answer 2

Эта строка выглядит неправильно

   if (Root == T_Nil)
        h = 1;

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

   if (Root->right == NULL && Root->left ==  NULL)
       h = 1;

Это узел, который не имеет дочерних элементов и, следовательно, имеет высоту 1.

Функция выглядит так, как будто она работает без этого оператора if, поскольку нулевое значение функции возвращает 0. Поскольку у нее уже есть +1 после MAX, я предполагаю, что это более правильное решение.