From: "Bad Beta" <cippedt@mindspring.com>
Subject: Help with Deletion (not lazy) from AVL Trees
Date: 1999/03/09
Date: 1999-03-09T06:47:40+00:00 [thread overview]
Message-ID: <7c2g6c$5e1$1@camel25.mindspring.com> (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;
next reply other threads:[~1999-03-09 0:00 UTC|newest]
Thread overview: 4+ messages / expand[flat|nested] mbox.gz Atom feed top
1999-03-09 0:00 Bad Beta [this message]
1999-03-09 0:00 ` Help with Deletion (not lazy) from AVL Trees Bad Beta
1999-03-11 0:00 ` Nick Roberts
1999-03-12 0:00 ` Joel VanLaven
replies disabled
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox