* Help with Deletion (not lazy) from AVL Trees
@ 1999-03-09 0:00 Bad Beta
1999-03-09 0:00 ` Bad Beta
0 siblings, 1 reply; 4+ messages in thread
From: Bad Beta @ 1999-03-09 0:00 UTC (permalink / raw)
I would greatly appreciate it if someone with more experience than me would
look over this code for deleting from AVL trees. I've tested a few times,
and everything seems to stay balanced. The deletion method is:
PROCEDURE Delete (T : IN OUT Tree; K : IN KeyType) IS
----------------------------------------------------------------------
--
--| ALV Tree Delete Operation (NOT LAZY), modification of Micheal B.
--| Feldman's BST Delete Operation.
--| Last Modified: March 1999
----------------------------------------------------------------------
--
Temp: Tree;
BEGIN -- Delete
IF T = NULL THEN
RAISE NotFound;
END IF;
IF K < KeyOf(T.Info) THEN -- check left subtree
Delete (T.Left, K);
IF (T.Right = NULL) AND (T.Left = NULL) THEN
RETURN;
END IF;
-- now rotate from this level, if necessary
IF (T /= NULL) AND THEN (Height(T.Right) - Height(T.Left) = 2)
THEN
IF T.Right.Left /= NULL THEN
Rotate_LR(T);
ELSE
Rotate_R(T);
END IF;
ELSE
T.Height := Max(Height(T.Left), Height(T.Right)); -- - 1;??
END IF;
ELSIF KeyOf(T.Info) < K THEN -- check right subtree
Delete (T.Right, K);
IF (T.Right = NULL) AND (T.Left = NULL) THEN
RETURN;
END IF;
-- now rotate from this level, if necessary
IF (T /= NULL) AND THEN (Height(T.Left) - Height(T.Right) = 2)
THEN
IF T.Left.Right /= NULL THEN
Rotate_RL(T);
ELSE
Rotate_L(T);
END IF;
ELSE
T.Height := Max(Height(T.Left), Height(T.Right)); -- - 1;
END IF;
ELSE -- delete this node
IF T.Left = NULL AND T.Right = NULL THEN
T := NULL; -- T is a leaf; delete it
ELSIF T.Right = NULL THEN -- replace T by its predecessor
T := T.Left;
ELSIF T.Left = NULL THEN -- replace T by its successor
T := T.Right;
ELSE -- both children there
Temp := FindSmallest(T.Right);
T.Info := Temp.Info;
Delete(T.Right, KeyOf(T.Info));
IF (T.Right = NULL) AND (T.Left = NULL) THEN
RETURN;
END IF;
-- now rotate from this level, if necessary
IF (T /= NULL) AND THEN (Height(T.Left) - Height(T.Right) =
2) THEN
IF T.Left.Right /= NULL THEN
Rotate_RL(T);
ELSE
Rotate_L(T);
END IF;
ELSE
T.Height := Max(Height(T.Left), Height(T.Right)); -- - 1;
END IF;
END IF;
END IF;
END Delete;
---Rotate Right is this method:
PROCEDURE Rotate_R (T: IN OUT Tree) IS
Temp: Tree := T.Right;
BEGIN -- Rotate_R
T.Right := Temp.Left;
Temp.Left := T;
T.Height := Max(Height(T.Right),Height(T.Left)) + 1;
Temp.Height := Max(Height(Temp.Right), T.Height) + 1;
T := Temp;
END Rotate_R;
--and Type Tree is Limited Private;
PRIVATE
TYPE AVLTreeNode;
TYPE Tree IS ACCESS AVLTreeNode;
TYPE AVLTreeNode IS RECORD
Info : Element;
Height : Natural := 0;
Left : Tree := NULL;
Right : Tree := NULL;
END RECORD;
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Help with Deletion (not lazy) from AVL Trees
1999-03-09 0:00 Help with Deletion (not lazy) from AVL Trees Bad Beta
@ 1999-03-09 0:00 ` Bad Beta
1999-03-11 0:00 ` Nick Roberts
0 siblings, 1 reply; 4+ messages in thread
From: Bad Beta @ 1999-03-09 0:00 UTC (permalink / raw)
Never mind...I already figured it out myself (The program's logic is
incorrect). Thanx anyway.
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Help with Deletion (not lazy) from AVL Trees
1999-03-09 0:00 ` Bad Beta
@ 1999-03-11 0:00 ` Nick Roberts
1999-03-12 0:00 ` Joel VanLaven
0 siblings, 1 reply; 4+ messages in thread
From: Nick Roberts @ 1999-03-11 0:00 UTC (permalink / raw)
I'm glad you have figured this one out. We are generally eager (possibly
sometimes slightly too eager :-) to help people with Ada problems here on
comp.lang.ada. Two things occur to me: it's funny how the same algorithm
can be expressed in so many (largely cosmetically) different ways, even in
the same language; most people use red-black trees rather than AVL trees
these days (often as a matter of fashion, I reckon), since (allegedly) RBTs
generally have better (search?) performance. (Oh and -- I don't mean this in
any kind of pejorative way -- but it's funny how you can tell a Modula
programmer/program who/that's been adapted to Ada :-)
-------------------------------------
Nick Roberts
-------------------------------------
^ permalink raw reply [flat|nested] 4+ messages in thread
* Re: Help with Deletion (not lazy) from AVL Trees
1999-03-11 0:00 ` Nick Roberts
@ 1999-03-12 0:00 ` Joel VanLaven
0 siblings, 0 replies; 4+ messages in thread
From: Joel VanLaven @ 1999-03-12 0:00 UTC (permalink / raw)
Nick Roberts wrote in message <7c7co9$nvt$3@plug.news.pipex.net>...
>Two things occur to me: it's funny how the same algorithm
>can be expressed in so many (largely cosmetically) different ways, even in
>the same language; most people use red-black trees rather than AVL trees
>these days (often as a matter of fashion, I reckon), since (allegedly) RBTs
>generally have better (search?) performance.
Hmm. It is my impression that the two common balanced binary tree
algorithms (well, the two I have run into) are AVL trees and 2-3-4 trees.
Both can be implemented as red-black trees. Assuming the red-black
implementation of each, I believe that 2-3-4 trees are simpler and can be
optimized for faster insertion (and deletion ?) Whereas AVL trees have a
better worst-case height (and hence in theory seach speed) but have more
complicated insertion.
In fact, I worked it out once and the worst case height of an AVL tree is
related to the Fibonnaci (why can't I spell that) sequence and through it
the golden ratio for about >
log base (1+sqrt(5))/2 (n) height where n is the number of nodes
On the other hand, red-black 2-3-4 trees are something like 2*log base 2 (n)
or rather log base sqrt(2) (n)
What is more, I belive that most 2-3-4 implementations will yield the worst
case in normal situations like sorted-order insertion whereas AVL trees will
not, it is a "wacky" order insertion that yields the worst case. I'm not
positive of that though.
-- Joel VanLaven
^ permalink raw reply [flat|nested] 4+ messages in thread
end of thread, other threads:[~1999-03-12 0:00 UTC | newest]
Thread overview: 4+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
1999-03-09 0:00 Help with Deletion (not lazy) from AVL Trees Bad Beta
1999-03-09 0:00 ` Bad Beta
1999-03-11 0:00 ` Nick Roberts
1999-03-12 0:00 ` Joel VanLaven
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox