jp.digitalmuseum.utils
クラス SplayTree<T>

java.lang.Object
  jp.digitalmuseum.utils.SplayTree<T>

型パラメータ:

T - Type of elements of the tree.

すべての実装されたインタフェース:

java.lang.Cloneable

public class SplayTree<T>

extends java.lang.Object

implements java.lang.Cloneable

A top-down splay tree based on Danny Sleator's implementation.

関連項目:

ftp://ftp.cs.cmu.edu/user/sleator/splaying/SplayTree.java}

入れ子のクラスの概要

static class

SplayTree.BinaryNode<T>

コンストラクタの概要

SplayTree(java.util.Comparator<T> comparator)

SplayTree(SplayTree.BinaryNode<T> root, java.util.Comparator<T> comparator)

SplayTree(SplayTree<T> splayTree)

メソッドの概要

void	clear()
SplayTree<T>	clone()
T	find(T x) Find an item in the tree.
T	findMax() Find the largest item in the tree.
T	findMin() Find the smallest item in the tree.
T	get(int index) Find an item which has the specified index.
boolean	insert(T x) Insert into the tree.
boolean	isEmpty() Test if the tree is logically empty.
boolean	join(SplayTree<T> splayTree) Merge two splay trees.
static void	main(java.lang.String[] args)
void	remove(T x) Remove from the tree.
int	size() Returns size of the tree.
SplayTree<T>	split(int index) Split the tree with the specified index.
SplayTree<T>	splitByValue(T x) Split the tree with the specified value.
java.lang.String	toString()

クラス java.lang.Object から継承されたメソッド

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

コンストラクタの詳細

SplayTree

public SplayTree(java.util.Comparator<T> comparator)

SplayTree

public SplayTree(SplayTree<T> splayTree)

SplayTree

public SplayTree(SplayTree.BinaryNode<T> root,
                 java.util.Comparator<T> comparator)

メソッドの詳細

insert

public boolean insert(T x)

Insert into the tree.

パラメータ:

x - the item to insert.

戻り値:

false if x is already present, otherwise true.

remove

public void remove(T x)

Remove from the tree.

パラメータ:

x - the item to remove.

例外:

ItemNotFoundException - if x is not found.

findMin

public T findMin()

Find the smallest item in the tree.

findMax

public T findMax()

Find the largest item in the tree.

find

public T find(T x)

Find an item in the tree.

パラメータ:

x - the item to find.

戻り値:

the item if found, otherwise null.

split

public SplayTree<T> split(int index)

Split the tree with the specified index.

パラメータ:

index - index of the separator item.

戻り値:

a new splay tree with items of the values greater than the item of the specified index.

splitByValue

public SplayTree<T> splitByValue(T x)

Split the tree with the specified value.

パラメータ:

x - the separator item.

戻り値:

a new splay tree with items of greater values.

get

public T get(int index)

Find an item which has the specified index.

パラメータ:

index - index of the item to find.

戻り値:

the item if found, otherwise null.

join

public boolean join(SplayTree<T> splayTree)

Merge two splay trees.

パラメータ:

splayTree - a splay tree to be merged.

戻り値:

whether the operation is succeeded or not.

isEmpty

public boolean isEmpty()

Test if the tree is logically empty.

戻り値:

true if empty, false otherwise.

clear

public void clear()

size

public int size()

Returns size of the tree.

戻り値:

size of the tree.

toString

public java.lang.String toString()

オーバーライド:

クラス java.lang.Object 内の toString

clone

public SplayTree<T> clone()

オーバーライド:

クラス java.lang.Object 内の clone

main

public static void main(java.lang.String[] args)