com.mhhe.clrs2e
Class BTree

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

All Implemented Interfaces:

Dictionary

public class BTree

extends java.lang.Object

implements Dictionary

Implementation of a B-tree from Chapter 18 of Introduction to Algorithms, Second edition. Objects inserted into a B-Tree must implement the DynamicSetElement interface.

Nested Class Summary

private static class	BTree.BTreeHandle Class to define a handle returned by searches.
private class	BTree.Node Private inner class for a B-tree node.

Field Summary

private int	maxKeys The maximum number of keys in any node, = 2t-1.
private BTree.Node	root The root of the B-tree.
private int	t The minimum degree, i.e., the minimum number of keys in any node other than the root.

Constructor Summary

BTree(int t)
Creates an empty B-tree.

Method Summary

void	delete(java.lang.Object key) Removes an element.
java.lang.Object	insert(java.lang.Comparable o) Inserts an element.
java.lang.Object	search(java.lang.Comparable k) Searches for an element with a given key.
java.lang.String	toString() Returns the String representation of this B-tree by walking it.

Methods inherited from class java.lang.Object

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

Field Detail

t

private final int t

The minimum degree, i.e., the minimum number of keys in any node other than the root.

maxKeys

private final int maxKeys

The maximum number of keys in any node, = 2t-1.

root

private BTree.Node root

The root of the B-tree.

Constructor Detail

BTree

public BTree(int t)

Creates an empty B-tree. Emulates B-Tree-Create on page 442.

Parameters:

t - The minimum degree of this B-tree.

Method Detail

search

public java.lang.Object search(java.lang.Comparable k)

Searches for an element with a given key.

Specified by:

search in interface Dictionary

Parameters:

k - The key being searched for.

Returns:

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

insert

public java.lang.Object insert(java.lang.Comparable o)

Inserts an element.

Specified by:

insert in interface Dictionary

Parameters:

o - The element to insert.

Returns:

A handle to the new element.

Throws:

java.lang.ClassCastException - if o does not reference a DynamicSetElement.

delete

public void delete(java.lang.Object key)

Removes an element.

The element to remove is specified by its key, rather than by a handle giving its location in the B-tree. We need to specify the object by its key because deletion from a B-tree works top-down, emulating a search. We need to use the path from the root down to the node containing the element to be deleted, and if we were given the element's node and index instead of its key, we would not be able to determine this path efficiently.

Specified by:

delete in interface Dictionary

Parameters:

key - The key of the element to remove.

Throws:

java.lang.ClassCastException - if key does not implement Comparable.

toString

public java.lang.String toString()

Returns the String representation of this B-tree by walking it.

Overrides:

toString in class java.lang.Object