From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.3 required=5.0 tests=BAYES_00,INVALID_MSGID
	autolearn=no autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,abc7dd97bf9a7dc7,start
X-Google-Attributes: gid103376,public
From: "Bad Beta" <cippedt@mindspring.com>
Subject: Help with Deletion (not lazy) from AVL Trees
Date: 1999/03/09
Message-ID: <7c2g6c$5e1$1@camel25.mindspring.com>#1/1
X-Deja-AN: 452877286
X-Server-Date: 9 Mar 1999 06:47:40 GMT
X-MimeOLE: Produced By Microsoft MimeOLE V4.72.3110.3
Organization: MindSpring Enterprises
Newsgroups: comp.lang.ada
Date: 1999-03-09T06:47:40+00:00
List-Id: <comp.lang.ada>

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;