Anonymous user
Talk:AVL tree/Java: Difference between revisions
no edit summary
No edit summary |
No edit summary |
||
Line 37:
}
</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.
| |||