Статья: Решение проблемы переполнения стека в AVL-дереве при вставке и удалении
Если вы столкнулись с ошибкой переполнения стека при работе с AVL-деревом в Pascal, то эта статья поможет вам решить эту проблему.
Описание проблемы
При использовании AVL-дерева для хранения и поиска данных могут возникать ошибки переполнения стека. Это происходит из-за бесконечной рекурсии при балансировке дерева. Ошибка #202 (stack overflow) возникает, когда стек переполняется и больше не может выделить память для новых функций.
Пример кода, вызывающий ошибку
Вот пример кода, который может вызвать ошибку переполнения стека при работе с AVL-деревом:
program Avl_generator; uses Crt;
type
p_Avl = ^Avl_node;
Avl_node = record
key: integer;
l, r, par: p_Avl;
bal, h: integer
end;
procedure init(var root: p_Avl);
begin
new(root);
root:=nil
end;
function get_height(var n: p_Avl): integer;
begin
if(n=nil) then get_height:=-1 else get_height:=n^.h;
end;
procedure reheight(var n: p_Avl);
begin
if(n<>) then
begin
if(get_height(n^.r)>get_height(n^.l)) then n^.h:=1+get_height(n^.r)
else n^.h:=1+get_height(n^.l);
end;
end;
procedure set_balance(var n: p_Avl);
begin
reheight(n);
n^.bal:=get_height(n^.r)-get_height(n^.l);
end;
function rotate_l(var a: p_Avl): p_Avl;
var
b: p_Avl;
begin
b := a^.r;
b^.par := a^.par;
a^.r := b^.l;
if(a^.r<>) then a^.r^.par := a;
b^.l := a;
a^.par := b;
if(b^.par<>) then
begin
if(b^.par^.r=a) then b^.par^.r := b
else b^.par^.l := b;
end;
set_balance(a);
set_balance(b);
rotate_l := b;
end;
function rotate_r(var a: p_Avl): p_Avl;
var
b: p_Avl;
begin
b := a^.l;
b^.par := a^.par;
a^.l := b^.r;
if(a^.l<>) then a^.l^.par := a;
b^.r := a;
a^.par := b;
if(b^.par<>) then
begin
if(b^.par^.r=a) then b^.par^.r := b
else b^.par^.l := b;
end;
set_balance(a);
set_balance(b);
rotate_r := b;
end;
function rotate_l_r(var a: p_Avl): p_Avl;
begin
a^.l := rotate_l(a^.l);
rotate_l_r := rotate_r(a);
end;
function rotate_r_l(var a: p_Avl): p_Avl;
begin
a^.r := rotate_r(a^.r);
rotate_r_l := rotate_l(a);
end;
procedure rebalance(var root: p_Avl; var n: p_Avl);
begin
set_balance(n);
if(n^.bal=-2) then
begin
if(get_height(n^.l^.l)>=get_height(n^.l^.r)) then n:=rotate_r(n)
else n:=rotate_l_r(n);
end
else if(n^.bal=2) then
begin
if(get_height(n^.r^.r)>=get_height(n^.r^.l)) then n:=rotate_l(n)
else n:=rotate_r_l(n);
end;
if(n^.par<>) then rebalance(root, n^.par) else root:=n;
end;
procedure insert(var root: p_Avl; what: integer);
var
found: boolean;
pre_tmp, tmp: p_Avl;
begin
found:=false; tmp:=root; pre_tmp:= nil;
while(tmp<>) and not found do
begin
if(tmp^.key=what) then found:=true
else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
else begin pre_tmp:=tmp; tmp:=tmp^.r end;
end;
if not found then
begin
new(tmp); tmp^.key:=what;
tmp^.l:=nil; tmp^.r:=nil; tmp^.par:=pre_tmp; tmp^.h:=0; tmp^.bal:=0;
if(pre_tmp=nil) then root:=tmp
else
begin
if(pre_tmp^.key>what) then pre_tmp^.l:=tmp else pre_tmp^.r:=tmp;
rebalance(root, pre_tmp);
end;
end;
end;
procedure delete(var root: p_Avl; what: integer);
var
found: boolean;
tmp, pre_tmp, act, pre_act: p_Avl;
begin
found:=false; tmp:=root; pre_tmp:=nil;
while(tmp<>) and not found do
begin
if(tmp^.key=what) then found:=true
else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
else begin pre_tmp:=tmp; tmp:=tmp^.r end;
end;
if found then
begin
if(tmp^.l=nil) then
begin
if(pre_tmp=nil) then root:=tmp^.r
else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.r
else pre_tmp^.r:=tmp^.r;
dispose(tmp);
rebalance(root,pre_tmp);
end
else if(tmp^.r=nil) then
begin
if(pre_tmp=nil) then root:=tmp^.l
else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.l
else begin pre_tmp^.r:=tmp^.l end;
dispose(tmp);
rebalance(root,pre_tmp);
end
else
begin
act:=tmp^.l; pre_act:=nil;
while(act^.r<>) do begin pre_act:=act; act:=act^.r end;
tmp^.key:=act^.key;
if(pre_act=nil) then begin tmp^.l:=act^.l; dispose(act); rebalance(root,tmp) end
else begin pre_act^.r:=act^.l; dispose(act); rebalance(root,pre_act) end;
end;
end;
end;
var
Avl_tree: p_Avl;
begin
init(Avl_tree);
insert(Avl_tree,1);
insert(Avl_tree,2);
insert(Avl_tree,3);
insert(Avl_tree,4);
insert(Avl_tree,5);
writeln(get_path(Avl_tree, 5));
repeat until KeyPressed;
end.
При добавлении или удалении элементов из дерева может возникнуть ошибка переполнения стека в процедурах rotate_l, rotate_r, rebalance, insert или delete.
Решение проблемы
Чтобы решить проблему переполнения стека при работе с AVL-деревом, нужно правильно реализовать процедуры балансировки дерева и корректно обрабатывать рекурсию.
Измените процедуры балансировки дерева
При балансировке дерева нужно правильно обрабатывать рекурсию, чтобы избежать бесконечной рекурсии и переполнения стека. В процедурах rotate_l, rotate_r, rotate_l_r и rotate_r_l нужно передавать параметры по значению, а не по ссылке. Это предотвратит ошибку, когда указатель на родительский узел станет недействительным после изменения указателя на дочерний узел.
Измените процедуры балансировки дерева следующим образом:
function rotate_l(a: p_Avl): p_Avl;
var
b: p_Avl;
begin
b := a^.r;
b^.par := a^.par;
a^.r := b^.l;
if(a^.r<>) then a^.r^.par := a;
b^.l := a;
a^.par := b;
if(b^.par<>) then
begin
if(b^.par^.r=a) then b^.par^.r := b
else b^.par^.l := b;
end;
set_balance(a);
set_balance(b);
rotate_l := b;
end;
function rotate_r(a: p_Avl): p_Avl;
var
b: p_Avl;
begin
b := a^.l;
b^.par := a^.par;
a^.l := b^.r;
if(a^.l<>) then a^.l^.par := a;
b^.r := a;
a^.par := b;
if(b^.par<>) then
begin
if(b^.par^.r=a) then b^.par^.r := b
else b^.par^.l := b;
end;
set_balance(a);
set_balance(b);
rotate_r := b;
end;
function rotate_l_r(a: p_Avl): p_Avl;
begin
a^.l := rotate_l(a^.l);
rotate_l_r := rotate_r(a);
end;
function rotate_r_l(a: p_Avl): p_Avl;
begin
a^.r := rotate_r(a^.r);
rotate_r_l := rotate_l(a);
end;
Измените процедуру ребалансировки дерева
При ребалансировке дерева нужно правильно обрабатывать рекурсию, чтобы избежать бесконечной рекурсии и переполнения стека. В процедуре rebalance нужно передавать параметры по значению, а не по ссылке. Это предотвратит ошибку, когда указатель на родительский узел станет недействительным после изменения указателя на дочерний узел.
Измените процедуру ребалансировки дерева следующим образом:
procedure rebalance(root: p_Avl; n: p_Avl);
begin
set_balance(n);
if(n^.bal=-2) then
begin
if(get_height(n^.l^.l)>=get_height(n^.l^.r)) then n:=rotate_r(n)
else n:=rotate_l_r(n);
end
else if(n^.bal=2) then
begin
if(get_height(n^.r^.r)>=get_height(n^.r^.l)) then n:=rotate_l(n)
else n:=rotate_r_l(n);
end;
if(n^.par<>) then rebalance(root, n^.par) else root:=n;
end;
Измените процедуры вставки и удаления элементов
При вставке и удалении элементов из дерева нужно правильно обрабатывать рекурсию, чтобы избежать бесконечной рекурсии и переполнения стека. В процедурах insert и delete нужно правильно вызывать процедуру ребалансировки дерева.
Измените процедуры вставки и удаления элементов следующим образом:
procedure insert(root: p_Avl; what: integer);
var
found: boolean;
pre_tmp, tmp: p_Avl;
begin
found:=false; tmp:=root; pre_tmp:= nil;
while(tmp<>) and not found do
begin
if(tmp^.key=what) then found:=true
else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
else begin pre_tmp:=tmp; tmp:=tmp^.r end;
end;
if not found then
begin
new(tmp); tmp^.key:=what;
tmp^.l:=nil; tmp^.r:=nil; tmp^.par:=pre_tmp; tmp^.h:=0; tmp^.bal:=0;
if(pre_tmp=nil) then root:=tmp
else
begin
if(pre_tmp^.key>what) then pre_tmp^.l:=tmp else pre_tmp^.r:=tmp;
rebalance(root, pre_tmp);
end;
end;
end;
procedure delete(root: p_Avl; what: integer);
var
found: boolean;
tmp, pre_tmp, act, pre_act: p_Avl;
begin
found:=false; tmp:=root; pre_tmp:=nil;
while(tmp<>) and not found do
begin
if(tmp^.key=what) then found:=true
else if(tmp^.key>what) then begin pre_tmp:=tmp; tmp:=tmp^.l end
else begin pre_tmp:=tmp; tmp:=tmp^.r end;
end;
if found then
begin
if(tmp^.l=nil) then
begin
if(pre_tmp=nil) then root:=tmp^.r
else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.r
else pre_tmp^.r:=tmp^.r;
dispose(tmp);
rebalance(root,pre_tmp);
end
else if(tmp^.r=nil) then
begin
if(pre_tmp=nil) then root:=tmp^.l
else if(pre_tmp^.key>what) then pre_tmp^.l:=tmp^.l
else begin pre_tmp^.r:=tmp^.l end;
dispose(tmp);
rebalance(root,pre_tmp);
end
else
begin
act:=tmp^.l; pre_act:=nil;
while(act^.r<>) do begin pre_act:=act; act:=act^.r end;
tmp^.key:=act^.key;
if(pre_act=nil) then begin tmp^.l:=act^.l; dispose(act); rebalance(root,tmp) end
else begin pre_act^.r:=act^.l; dispose(act); rebalance(root,pre_act) end;
end;
end;
end;
Вывод
При работе с AVL-деревом в Pascal могут возникать ошибки переполнения стека из-за бесконечной рекурсии при балансировке дерева. Чтобы решить эту проблему, нужно правильно реализовать процедуры балансировки дерева и корректно обрабатывать рекурсию. В этой статье мы рассмотрели, как изменить процедуры балансировки дерева, процедуру ребалансировки дерева и процедуры вставки и удаления элементов, чтобы избежать ошибки переполнения стека при работе с AVL-деревом в Pascal.
Контекст: Статья описывает решение проблемы переполнения стека, возникающей при работе с AVL-деревом в Pascal при вставке и удалении элементов.
Комментарии и вопросы
Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS
Telegram-канал