#c# #data-structures #binary-search-tree
Вопрос:
Я столкнулся с интересной ошибкой при создании BST «оптимизированного для поиска» (у каждого узла есть идентификатор количества доступа). Я могу успешно перемещать узлы вверх по дереву, однако некоторые узлы перемещаются вверх по дереву не так часто, как ожидалось.
Например:
Когда я вызываю свой метод поиска по значению 1 , дерево успешно настраивается, и 1 становится корнем. Впоследствии, когда я вызываю метод на 4 узле, узел становится правым дочерним по отношению к корню 1 .
Однако, когда я вызываю 5 или 6 узел поворачивается вверх только один раз, оптимизация заканчивается.
Вот мой код, который оптимизирует дерево, он вызывается в корне дерева после того, как узел найден с помощью метода find:
private void RecOptimize(TreeNode<T> currentNode, TreeNode<T> prevNode)
{
if (currentNode == null) return;
RecOptimize(currentNode.left, currentNode);
RecOptimize(currentNode.right, currentNode);
var left = currentNode.left;
var right = currentNode.right;
var oldNode = currentNode;
if(right != null)
{
if (right.iAccessCount > currentNode.iAccessCount)
{
currentNode = MakeRightRoot(currentNode);
}
}
if(left != null)
{
if (left.iAccessCount > currentNode.iAccessCount)
{
currentNode = MakeLeftRoot(currentNode);
}
}
if(prevNode != null)
{
if(prevNode.left != null amp;amp; prevNode.left.Equals(oldNode))
{
prevNode.left = currentNode;
}
if(prevNode.right != null amp;amp; prevNode.right.Equals(oldNode))
{
prevNode.right = currentNode;
}
}
else
{
this.rootNode = currentNode;
}
}
Я подумал, что хотел бы кое-что прояснить.
MakeLeftRoot(node) и MakeRightRoot(node) просто выполните вращение вокруг узла, MakeLeftRoot поверните узлы влево и верните его. While MakeRightRoot делает то же самое, но с правой стороны.
Правка 2 Здесь приведен код для методов вращения
protected TreeNode<T> MakeRightRoot(TreeNode<T> oldRoot)
{
var newRoot = oldRoot.right;
oldRoot.right = newRoot.left;
newRoot.left = oldRoot;
return newRoot;
}
protected TreeNode<T> MakeLeftRoot(TreeNode<T> oldRoot)
{
var newRoot = oldRoot.left;
oldRoot.left = newRoot.right;
newRoot.right = oldRoot;
return newRoot;
}
Комментарии:
1. Примечание сбоку: зачем вам для этого перебирать все дерево? Вы должны сделать это в функции поиска, так как именно там увеличивается счетчик доступа (я полагаю), и поэтому это единственный путь, который может потребовать поворота. Во-вторых, вы должны предоставить нам достаточно кода, чтобы воспроизвести проблему.
Ответ №1:
Я буду считать, что весь ваш остальной код верен, включая функции, выполняющие вращения. Тогда все еще существует эта проблема в RecOptimize :
Если currentNode изменения происходят по вызову MakeRightRoot(currentNode) , то left right переменные и больше не представляют левый и правый узлы currentNode , и поэтому следующий if блок не будет делать то, что задумано, так как в этот момент left является внуком currentNode .
Я понимаю, почему вы также передаете prevNode в эту функцию, и как if(prevNode != null) блок имеет дело с установкой ссылке С prevNode и потенциально изменить ведения currentNode , но это будет намного проще, если вы используете тот же шаблон кодирования, как для вращения, функции: пусть функция возврата потенциально изменить ведения currentNode , и пусть абонент несет ответственность за присоединение этот узел обратно в родительский узел.
Кроме того, вы должны определить, возможно ли, что в обоих поддеревьях узла происходит большее количество обращений, или нет. Если это не может произойти (потому что после каждого доступа вы вызываете эту функцию), то вы можете использовать if ...else if конструкцию для двух первых блоков. Если, однако, это может произойти, то подумайте, как вы хотите, чтобы дерево поворачивалось. Я считаю, что лучше затем иметь дело с каждым поддеревом отдельно: сначала полностью завершите работу для одного поддерева (рекурсивный вызов потенциальное вращение), а затем только с другим поддеревом (рекурсивный вызов потенциальное вращение).
Вот предлагаемый код:
private TreeNode<T> RecOptimize(TreeNode<T> node) {
if (node == null) return null;
if (node.right != null) {
node = RecOptimize(node.right);
if (node.right.iAccessCount > node.iAccessCount) {
node = MakeRightRoot(node);
}
}
if (node.left != null) {
node = RecOptimize(node.left);
if (node.left.iAccessCount > node.iAccessCount) {
node = MakeLeftRoot(node);
}
}
return node;
}
Основной вызов:
this.rootNode = RecOptimize(this.rootNode);
Еще один комментарий: RecOptimize собирается посетить каждый узел в дереве. Это не оптимально. Если вы получаете доступ к узлу с помощью двоичного поиска, то вам нужно будет только проверить вращение вдоль пути к этому найденному узлу в качестве фазы «всплывания».
Комментарии:
1. Это решение действительно работает, но теперь я думаю, что у меня проблема с моей ротацией. Я опубликовал код, извините, что пропустил его раньше. Кроме того, где бы я назвал это во время фазы всплеска? Мне трудно понять, где происходит рекурсивное отслеживание, если у вас есть какие-либо сведения об этом, которые были бы потрясающими!
2. Могу ли я предложить вам задать новый, специальный вопрос о ротации с примером, в котором проблема становится очевидной? И если вы не можете заставить пузырящуюся версию работать, можете ли вы задать еще один вопрос об этом, показывающий вашу работу и то, где вы застряли?