Talk:AVL tree/Java: Difference between revisions
Content added Content deleted
No edit summary |
No edit summary |
||
Line 37: | Line 37: | ||
} |
} |
||
</lang> |
</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. |