Package aud

Class A234Tree<Key extends Comparable<Key>>

java.lang.Object

aud.A234Tree<Key>

All Implemented Interfaces:

Graphvizable

public class A234Tree<Key extends Comparable<Key>>
extends Object
implements Graphvizable

Simple implementation of 2-3-4-trees based on KTreeNode. Note that in contrast to BinarySearchTree ...

• we store only keys rather than key-value pairs.
• there is no dummy node head, there is no reference to parents.

The class implements insertion with top-down and bottom-up splits. The strategy for splitting is selected at construction.

• In top-down mode, insert(Key) calls the recursive insert_top_down(aud.KTreeNode<Key>, Key), which splits all 4-nodes (using split_top_down(aud.KTreeNode<Key>)) on the way down to the insertion position. (This may split the root!) So the final KTreeNode.insert(Key, int) is guaranteed to not cause a split.
• In bottom-up mode, insert(Key) calls the recursive insert_bottom_up(aud.KTreeNode<Key>, Key), which inserts first and splits if the new node is a 5-node (recursive split_bottom_up(aud.KTreeNode<Key>,int)).
  Note that this is sort of cheating for ease of implementation because in a proper 2-3-4-tree, there cannot be 5-nodes! (We use KTreeNode.) This has the side effect, that the selection of the node that is "pulled up" to the parent by KTreeNode.mergeChild(int)) possibly has to be "corrected" if the insertion position was less than 2.

Note that there is currently no operation for removal. (This would cause KTreeNode.mergeChild(int).)

Constructor Summary

Constructors

Constructor	Description
A234Tree()	create an empty 2-3-4-tree
A234Tree(boolean top_down)	create an empty 2-3-4-tree and select insertion strategy

Method Summary

Modifier and Type	Method	Description
void	checkConsistency()	few consistency checkschild.entries_.at(i).child
Key	find(Key key)	find key in tree
boolean	insert(Key key)	insert entry
protected boolean	insert_bottom_up(KTreeNode<Key> node, Key key)
protected boolean	insert_top_down(KTreeNode<Key> node, Key key)
static void	main(String[] args)	example and test
protected void	onSplit(KTreeNode<Key> node)	callback invoked by split_bottom_up(aud.KTreeNode<Key>,int) or split_top_down(aud.KTreeNode<Key>), default implementation is empty
protected void	split_bottom_up(KTreeNode<Key> node, int pos)	Split 5-node and merges with parent.
protected KTreeNode<Key>	split_top_down(KTreeNode<Key> node)	Split 4-node and merges with parent.
String	toDot()	Get dot representation.
String	toString()
String	toTikZ()	get TikZ code for LaTeX export (calls KTreeNode.toTikZ())

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Details

A234Tree

public A234Tree()

create an empty 2-3-4-tree

A234Tree

public A234Tree(boolean top_down)

create an empty 2-3-4-tree and select insertion strategy

Method Details

find

public Key find(Key key)

find key in tree

Returns:

found key, note that this is generally a different instance than key! (We have "only" compareKeys()==0.)

insert

public boolean insert(Key key)

insert entry

Returns:

true if key was not an entry of child before

split_bottom_up

protected void split_bottom_up(KTreeNode<Key> node,
 int pos)

Split 5-node and merges with parent.

• I'm sort of cheating here: I let a node eventually become a 5-node and split only then. Implementation is simpler, but it's not (storage) efficient!
• The pos argument stores the insertion position into the 5-node before splitting. It is used to correctly determine the index of the element that is "pulled up".
• This may lead to a recursive split up to the root.
• The method has no effect on 2- and 3-nodes.
• split calls onSplit(aud.KTreeNode<Key>) before the split.

split_top_down

protected KTreeNode<Key> split_top_down(KTreeNode<Key> node)

Split 4-node and merges with parent.

• This method is called on insert(Key) while traversing top-down.
• split calls onSplit(aud.KTreeNode<Key>) before the split.

Returns:

node (no split) or its parent (on slit), such that insertion "continues" at returned node

onSplit

protected void onSplit(KTreeNode<Key> node)

callback invoked by split_bottom_up(aud.KTreeNode<Key>,int) or split_top_down(aud.KTreeNode<Key>), default implementation is empty

insert_bottom_up

protected boolean insert_bottom_up(KTreeNode<Key> node,
 Key key)

insert_top_down

protected boolean insert_top_down(KTreeNode<Key> node,
 Key key)

toDot

public String toDot()

Description copied from interface: Graphvizable

Get dot representation.

Specified by:

toDot in interface Graphvizable

toTikZ

public String toTikZ()

get TikZ code for LaTeX export (calls KTreeNode.toTikZ())

toString

public String toString()

Overrides:

toString in class Object

checkConsistency

public void checkConsistency()

few consistency checkschild.entries_.at(i).child

Throws:

RuntimeException - on error (and/or assertion fails)

main

public static void main(String[] args)

example and test