Talk:AVL tree/Java

The Java version was ported from C# in 2016. The port of the full Calculus class library took only a week. [User:NNcNannara|NNcNannara]] (talk) 10:20, 11 July 2016 (UTC)

The abbreviated version of Java on the main page will suffer in performance just like the C++ version on the main page - see C++ Talk.

The Java implementation of AVL Trees is a bit different to the C# version in that references to references are not available. This means that functions like RotateLeft and RotateRight return the new node rather than the function updating the reference for you. It is only a cosmetic change to the code. NNcNannara (talk) 11:25, 16 July 2016 (UTC)

AVL on Disk can be implemented in Java (i.e. AVL Databases). There are 12 databases in Calculus. Strangely enough, all 12 databases use the same basic node type on disk. The definition of that node type is shown below.

<lang Java> public class Node

   {
       public long Left;
       public long Right;
       public long Parent;
       public long Key;
       public State Balance;

       public Node()
       {
           Left = 0;
           Right = 0;
           Parent = 0;
           Balance = State.Header;
           Key = 0;
       }
       
       public Node(long p)
       {
           Left = 0;
           Right = 0;
           Parent = p;
           Balance = State.Balanced;
           Key = 0;
       }

       public Boolean IsHeader ()  { return Balance == State.Header; }
   }

</lang>

Present are offsets for the Left, Right and Parent nodes - which are offsets into the node file. Also present is the Key offset, which is an offset into a separate data file. The balance factor is an enum of 4 states. Strictly speaking, when on disk the Header state is not required to identify the header node because it is at offset zero. However, to be consistent with the in-memory calculus, we use a Header state to identify the header node.

Once the header node is defined, you can go right ahead and produce the AVL Balancing Utilities. For example, a left rotation is as follows. <lang java>

       static long RotateLeft(NodeFile nf, long node) throws IOException
       {
           Node Node = nf.Get(node);
           long parent = Node.Parent;
           long x = Node.Right;
           Node X = nf.Get(x);
           Node.Parent = x;
           X.Parent = parent;
           if (X.Left != 0)
           {
               Node XLeft = nf.Get(X.Left);
               XLeft.Parent = node;
               nf.Update(X.Left, XLeft);
           }
           Node.Right = X.Left;
           X.Left = node;
           nf.Update(node, Node);
           nf.Update(x, X);
           return x;
       }

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