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)


Copyright by Jun KATO (arc@dmz) at http://mr.digitalmuseum.jp/