Help with Deletion (not lazy) from AVL Trees

Help with Deletion (not lazy) from AVL Trees

[Bad Beta]

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;

Re: Help with Deletion (not lazy) from AVL Trees

[Bad Beta]

Never mind...I already figured it out myself (The program's logic is
incorrect).  Thanx anyway.

Re: Help with Deletion (not lazy) from AVL Trees

[Nick Roberts]

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
-------------------------------------

Re: Help with Deletion (not lazy) from AVL Trees

[Joel VanLaven]

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