com.mhhe.clrs2e
Class BTree.Node

java.lang.Object
  |
  +--com.mhhe.clrs2e.BTree.Node

Enclosing class:

BTree

private class BTree.Node

extends java.lang.Object

Private inner class for a B-tree node.

Field Summary

BTree.Node[]	c Pointers to the children, if this node is not a leaf.
com.mhhe.clrs2e.DynamicSetElement[]	key Array of the keys stored in the node.
boolean	leaf true if this node is a leaf, false if this node is an interior node.
int	n The number of keys stored in the node.

Constructor Summary

BTree.Node(int n, boolean leaf)
Initializes the instance variables, including allocating the c array if this node is not a leaf.

Method Summary

BTree.BTreeHandle	BTreeInsertNonfull(com.mhhe.clrs2e.DynamicSetElement k) Inserts a new element in this node, which is assumed to be nonfull.
BTree.BTreeHandle	BTreeSearch(java.lang.Comparable k) Searches for a dynamic set element with a given key, starting at this node.
void	BTreeSplitChild(BTree.Node x, int i) Splits this node, which is a full child of its parent, which is in turn a nonfull internal node.
void	delete(java.lang.Comparable k) Deletes an element with a given key from the subtree rooted at this node.
private void	deleteFromInternalNode(int i) Deletes a given key from this node, which is assumed to be an internal node and already in memory.
private void	deleteFromLeaf(java.lang.Comparable k) Deletes an element with a given key from this node, which is assumed to be a leaf and already in memory.
private void	diskRead() Reads a disk block.
void	diskWrite() Writes a disk block.
private void	ensureFullEnough(int i) Ensures that a given child of this node child has at least t keys.
private com.mhhe.clrs2e.DynamicSetElement	findGreatestInSubtree() Finds the dynamic set element with the greatest key in the subtree rooted at this node.
private com.mhhe.clrs2e.DynamicSetElement	findSmallestInSubtree() Finds the dynamic set element with the smallest key in the subtree rooted at this node.
private void	free() Frees this node.
java.lang.String	walk(int depth) Returns the String representation of the subtree rooted at this node.

Methods inherited from class java.lang.Object

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

Field Detail

n

public int n

The number of keys stored in the node.

key

public com.mhhe.clrs2e.DynamicSetElement[] key

Array of the keys stored in the node.

c

public BTree.Node[] c

Pointers to the children, if this node is not a leaf. If this node is a leaf, then null.

leaf

public boolean leaf

true if this node is a leaf, false if this node is an interior node.

Constructor Detail

BTree.Node

public BTree.Node(int n,
                  boolean leaf)

Initializes the instance variables, including allocating the c array if this node is not a leaf.

Parameters:

n - How many of keys are to be stored in this node.

leaf - true if this node is a leaf, false if this node is an interior node.

Method Detail

diskRead

private void diskRead()

Reads a disk block. Does nothing in this implementation. You should customize it for your system.

diskWrite

public void diskWrite()

Writes a disk block. Does nothing in this implementation. You should customize it for your system.

free

private void free()

Frees this node. Does nothing in this implementation. You should customize it for your system.

BTreeSearch

public BTree.BTreeHandle BTreeSearch(java.lang.Comparable k)

Searches for a dynamic set element with a given key, starting at this node.

Parameters:

k - The key.

Returns:

A handle to the object found, or null if there is no match.

BTreeSplitChild

public void BTreeSplitChild(BTree.Node x,
                            int i)

Splits this node, which is a full child of its parent, which is in turn a nonfull internal node. We assume that both this node and its parent are already in main memory. This method splits this node in two and adjusts the parent so that it has an additional child.

Parameters:

x - This node's parent.

i - This node is child c[i] of x.

BTreeInsertNonfull

public BTree.BTreeHandle BTreeInsertNonfull(com.mhhe.clrs2e.DynamicSetElement k)

Inserts a new element in this node, which is assumed to be nonfull.

Parameters:

k - The new element to be inserted.

delete

public void delete(java.lang.Comparable k)

Deletes an element with a given key from the subtree rooted at this node.

Parameters:

k - The key of an element to be deleted.

deleteFromLeaf

private void deleteFromLeaf(java.lang.Comparable k)

Deletes an element with a given key from this node, which is assumed to be a leaf and already in memory. Does nothing if this node does not contain an element with the given key.

Parameters:

k - The key of the element to be deleted.

deleteFromInternalNode

private void deleteFromInternalNode(int i)

Deletes a given key from this node, which is assumed to be an internal node and already in memory.

Parameters:

i - key[i] is deleted from this node.

findGreatestInSubtree

private com.mhhe.clrs2e.DynamicSetElement findGreatestInSubtree()

Finds the dynamic set element with the greatest key in the subtree rooted at this node. Works by always taking the rightmost child until we get to a leaf. Assumes that this node is already in memory.

Returns:

The dynamic set element with the greatest key in the subtree rooted at this node.

findSmallestInSubtree

private com.mhhe.clrs2e.DynamicSetElement findSmallestInSubtree()

Finds the dynamic set element with the smallest key in the subtree rooted at this node. Works by always taking the leftmost child until we get to a leaf. Assumes that this node is already in memory.

Returns:

The dynamic set element with the smallest key in the subtree rooted at this node.

ensureFullEnough

private void ensureFullEnough(int i)

Ensures that a given child of this node child has at least t keys. Assumes that this node and the child are already in memory.

Parameters:

i - The ith child of this node is the one that will have at last t keys.

walk

public java.lang.String walk(int depth)

Returns the String representation of the subtree rooted at this node. Represents the depth of each node by two spaces per depth preceding the String representation of the node.