|
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. [[User:NNcNannara|NNcNannara]] ([[User talk: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 [http://nncnannara.net/Html/English/Java/persist/index.html Applied 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 class 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.
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.
Using the above definition of nodes, it is possible to produce all the classes in [http://nncnannara.net/Html/English/Java/persist/index.html Applied Calculus]. Note that unordered collections such as [http://nncnannara.net/Html/English/Java/persist/Table.html Table] and [http://nncnannara.net/Html/English/Java/persist/Map.html Map] are possible. This is because of a type of hashing known as Binary Hashing, where hash tables are implemented using AVL Trees. That is, Unordered Calculus has been derived from Ordered Calculus using Binary Hashing.[[User:NNcNannara|NNcNannara]] ([[User talk:NNcNannara|talk]]) 11:06, 11 March 2017 (UTC)
|