Решение проблемы с родительской ссылкой в AVL-дереве на Паскале

Delphi , Синтаксис , Деревья

При программировании AVL-дерева на Паскале одной из проблем, с которой можно столкнуться, является правильная настройка родительских ссылок при вращениях поддерева. В этой статье мы рассмотрим, как эффективно решить эту проблему.

Введение

AVL-дерево — это сбалансированное бинарное дерево, в котором высота левого и правого поддерева отличается не более чем на 1. Для поддержания сбалансированности используются вращения поддеревьев. Однако при вращениях может возникнуть проблема с правильной настройкой родительских ссылок.

Проблема с родительской ссылкой

Рассмотрим следующее дерево:

        55
      /   \
    30    60
   /  \  /  \
  10  45 50  75
 /  \  / \
5  15 50  90

При вращении поддерева с корнем 30, мы хотим изменить родительскую ссылку от 55 к 45. Однако, в большинстве случаев, код, который вы видели, не имеет ссылки на родителя для узла, что делает изменение родительской ссылки непонятным.

Решение проблемы

Для решения этой проблемы нужно понимать, как происходит вращение поддерева. При вращении поддерева с корнем 30, мы создаем новый корень 45 и меняем родительскую ссылку от 55 к 45. Однако, для этого нам нужен доступ к родительскому узлу 55.

Вот как это можно сделать на Паскале:

type
  TNode = ^TNodeRecord;
  TNodeRecord = record
    Value: Integer;
    Left, Right, Parent: TNode;
    Height: Integer;
  end;

procedure RotateLeft(var Node: TNode);
var
  Parent, Grandparent, Temp: TNode;
begin
  Parent := Node.Right;
  Node.Right := Parent.Left;
  Parent.Left := Node;

  Temp := Parent.Left;
  Parent.Left := Temp.Right;
  Temp.Right := Parent;

  Node := Parent;

  // Обновляем высоту узлов
  Node.Height := (Node.Left^.Height + Node.Right^.Height + 1);
  Parent.Height := (Parent.Left^.Height + Parent.Right^.Height + 1);
  Temp.Height := (Temp.Left^.Height + Temp.Right^.Height + 1);
end;

procedure RotateRight(var Node: TNode);
var
  Parent, Grandparent, Temp: TNode;
begin
  Parent := Node.Left;
  Node.Left := Parent.Right;
  Parent.Right := Node;

  Temp := Parent.Right;
  Parent.Right := Temp.Left;
  Temp.Left := Parent;

  Node := Parent;

  // Обновляем высоту узлов
  Node.Height := (Node.Left^.Height + Node.Right^.Height + 1);
  Parent.Height := (Parent.Left^.Height + Parent.Right^.Height + 1);
  Temp.Height := (Temp.Left^.Height + Temp.Right^.Height + 1);
end;

procedure BalanceTree(var Node: TNode);
begin
  Node.Height := (Node.Left^.Height + Node.Right^.Height + 1);

  if Node.Left^.Height - Node.Right^.Height > 1 then
  begin
    if Node.Left^.Left^.Height > Node.Left^.Right^.Height then
      RotateRight(Node)
    else
    begin
      RotateLeft(Node.Left);
      RotateRight(Node);
    end;
  end
  else if Node.Right^.Height - Node.Left^.Height > 1 then
  begin
    if Node.Right^.Right^.Height > Node.Right^.Left^.Height then
      RotateLeft(Node)
    else
    begin
      RotateRight(Node.Right);
      RotateLeft(Node);
    end;
  end;
end;

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

Альтернативное решение

Другой подход к решению этой проблемы — использование дополнительного поля в структуре узла, которое будет содержать ссылку на родителя. Это позволяет легко изменить родительскую ссылку при вращении поддерева.

type
  TNode = ^TNodeRecord;
  TNodeRecord = record
    Value: Integer;
    Left, Right: TNode;
    Parent: TNode;
    Height: Integer;
  end;

procedure RotateLeft(var Node: TNode);
begin
  // ... (остальной код вращения остается без изменений)

  Node.Parent := Parent.Parent;
  Parent.Parent := Node;
end;

procedure RotateRight(var Node: TNode);
begin
  // ... (остальной код вращения остается без изменений)

  Node.Parent := Parent.Parent;
  Parent.Parent := Node;
end;

В этом подходе, мы добавляем поле Parent в структуру узла, которое содержит ссылку на родительский узел. При вращении поддерева, мы просто меняем родительскую ссылку для нового корня поддерева и родительского узла.

Заключение

В этой статье мы рассмотрели проблему настройки родительских ссылок при вращениях поддеревьев в AVL-дереве на Паскале. Мы предложили два решения этой проблемы: первое — использование процедур вращения, которые находят родительский узел и меняют родительскую ссылку; второе — использование дополнительного поля в структуре узла, которое содержит ссылку на родителя. Каждое из этих решений имеет свои преимущества и недостатки, и выбор между ними зависит от конкретной задачи и предпочтений разработчика.

Создано по материалам из источника по ссылке.

В этой статье рассматривается решение проблемы настройки родительских ссылок при вращениях поддеревьев в AVL-дереве на Паскале.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Деревья ::