Блог

Я внедряю красно-черное дерево для целей университетов, и я застрял на том свойстве, что каждый путь от корня до листа должен иметь одинаковое количество черных узлов. Я вставил все необходимые функции : fixup, rotation, insertion …Но я не знаю, как справиться с этой функцией. Я думал о чем-то вроде :

 void checkNuberBlackNodes(struct node* root) {
    if( numberBlackNodes(root->right) > numberBlackNodes(root->left) {
         leftRotate(root);
         colorize(root);
    }
    else if( numberBlackNodes(root->right) < numberBlackNodes(root->left) {
         rightRotate(root);
         colorize(root);
    }
    else return; //no violation, same number of black nodes
}
 

Идея заключается в том, чтобы insert на узел, fix up нарушающий, а затем checkNumberBlackNodes на новый вставленный узел (или из корневого).
Я не знаю, как справиться с этим процессом, все предыдущие функции были довольно просты в реализации…Я не знаю, с чего бы мне начать.
Правка : У меня появилась новая идея :

 void checkNuberBlackNodes(struct node* root) {
  int diff = height(root->right) - height(root->left);
  if ( diff >=2 ) //if the tree is too deep
  {
     leftRotate(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
  else if ( diff <= -2 ) //specular case
  { 
     rightRotate(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
  else if( blackHeight(root->right) > blackHeight(root->left) {
     colorize(root->right);
     checkNuberBlackNodes(root->right);
     return;
  }
else if( blackHeight(root->right) < blackHeight(root->left) {
     colorize(root->left);
     checkNuberBlackNodes(root->left);
     return;
  }
else return; //No violation
}
 

blackHeight является ли количество черных узлов на этом пути от узла к листу;

Если вы вставляете новый узел в красно-черное дерево, этот узел всегда является конечным узлом в конце. И неизменно он окрашен в красный цвет.

Обычно

(1) Вставка узла может нарушить правило «нет последовательных красных узлов», и исправления будут выполняться в направлении корня. Требуется не более 2 оборотов и 3 * O(h/2) перекраски, где h-высота дерева. Если родительский элемент вставленного узла черный, никаких исправлений не требуется.

(2) Удаление узла может нарушить правило «количество черных узлов от корня вниз по каждому пути одинаково». Опять же, исправления происходят в направлении к корню. Требуется не более 3 оборотов и O(h) перекрасок, где h-высота дерева.

Если удаляемый узел является корневым узлом без дочерних узлов, удалите его.

Если у удаляемого узла есть два дочерних элемента, найдите непосредственного преемника (правый дочерний элемент, затем полностью влево), поменяйте местами Узел и узел-преемник (но СОХРАНИТЕ исходные цвета узлов). Следующим узлом всегда будет узел с 0 дочерними узлами или 1 дочерним узлом. Теперь вам нужно удалить исходный узел, но в положении преемника. Вы переходите к следующим двум делам.

Если удаленный узел является конечным узлом и имеет красный цвет, исправления не требуются, удалите узел

Если у удаляемого узла есть один дочерний элемент, он черный, дочерний элемент красный, удалите узел, замените Узел дочерним, перекрасьте дочерний элемент в черный цвет.

Так что же из этого остается? Это оставляет черный узел, который является конечным узлом, без детей, сложный случай. Удаление этого нарушит правило «количество черных узлов от корня вниз по каждому пути одинаково».

Удалив узел, родительский узел теперь имеет неправильное количество черных путей с одной стороны дерева. По сути, удаление-это двусторонняя стратегия:

а) Вы проверяете родительский узел, узел-брат и узлы-дети-братья, чтобы увидеть, есть ли красные. Если это так, вы можете с помощью поворотов и перекраски изменить это, чтобы черная дыра на удаленной стороне была заполнена заново, восстанавливая дерево. б) и если все узлы (или НУЛЕВЫЕ узлы) черные, то вы делаете узел-брат красным, а родительский узел теперь считается точкой для восстановления дерева. Вы сделали обе стороны дерева одинаково плохими, и теперь точка исправления на 1 уровень выше. Вы возвращаетесь к шагу а) , поскольку появилось новое определение понятий «родитель», «родной брат» и «дети-братья». в) Возможно иметь красно-черное дерево, которое полностью черное. Что произойдет, если вы достигнете корня и не встретите красных узлов? Тогда это теперь красно-черное дерево. По сути , изменение братьев и сестер привело к появлению 1 красного узла на каждом пути дерева, что равномерно уменьшило высоту черного дерева на 1 везде.