Talk:AVL tree/Java: Difference between revisions

Content added Content deleted

Inline

@@ Line 64: / Line 64: @@
 </lang>
 Once you recode all the utilities, you can formulate AVL on disk, i.e. AVL Databases. The first database to consider is Set - the on-disk version of the in-memory source code contained in this Wiki. Once you have Set, you can do Tree, Dictionary etc.
+Rather than the convoluted iteration scheme of B+, AVL Trees on disk may be iterated courtesy of parent references as follows.
+<lang Java>
+static long NextSlot(NodeFile nf, long slot) throws IOException
+        {
+            Node Slot = nf.Get(slot);
+            if (slot == 0)
+                return Slot.Left;
+            else
+            {
+                if (Slot.Right != 0)
+                {
+                    slot = Slot.Right;
+                    Slot = nf.Get(slot);
+                    while (Slot.Left != 0)
+                    {
+                        slot = Slot.Left;
+                        Slot = nf.Get(slot);
+                    }
+                }
+                else
+                {
+                    long y = Slot.Parent;
+                    if (y == 0)
+                        return y;
+                    else
+                    {
+                        Node Y = nf.Get(y);
+                        while (slot == Y.Right)
+                        {
+                            slot = y;
+                            y = Y.Parent;
+                            if (y == 0) break;
+                            Y = nf.Get(y);
+                        }
+                        slot = y;
+                    }
+                }
+                return slot;
+            }
+        }
+</lang>
+For AVL Trees, iteration is achieved through the use of parent references. For B+ Trees, the key is stored twice and the leaves form a double linked list (and B+ Trees have no parent references). This is all rather awkward compared to the elegant solution that AVL Trees offer.