|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--gishur.core.BasicTree | +--gishur.core.BinarySearchTree
A binary search tree based upon BasicTree
. To ensure that the tree
is ordered, a BinarySearchTree
-object needs a Comparitor
when
being constructed. Only objects comparable with the specified Comparitor
should be stored in the tree, otherwise there will somewhen occur a
CompareException
. If the empty constructor BinarySearchTree()
is
called, a StdComparitor
is created and used.
Fields inherited from class gishur.core.BasicTree |
_access, ANY_ACCESS, CHILDS_ROOT_ORDER, KEY, LEFT_RIGHT_ROOT_ORDER, LEFT_ROOT_RIGHT_ORDER, NO_ACCESS, ROOT_CHILDS_ORDER, ROOT_LEFT_RIGHT_ORDER, TREEITEM, VALUE |
Fields inherited from interface gishur.core.ControlledCloneable |
DEEP, FLAT |
Constructor Summary | |
BinarySearchTree()
Empty constructor. |
|
BinarySearchTree(Comparitor comparitor)
Standard constructor. |
|
BinarySearchTree(Comparitor comparitor,
boolean left_is_smaller)
Constructs a BinarySearchTree using the Comparitor comparitor
and the definition whether smaller keys shall be sorted to the left or to
the right side of the tree. |
Method Summary | |
protected TreeItem |
add_item(TreeItem item)
Inserts a new TreeItem into the tree. |
TreeItem |
add(boolean n)
add for boolean . |
TreeItem |
add(double n)
add for double . |
TreeItem |
add(float n)
add for float . |
TreeItem |
add(int n)
add for int . |
TreeItem |
add(long n)
add for long . |
TreeItem |
add(java.lang.Object key)
Inserts a newly generated TreeItem with key key into the tree
at the right place.
|
TreeItem |
add(java.lang.Object key,
java.lang.Object value)
Inserts a newly generated TreeItem with key and value into the
tree at the right place.
|
TreeItem |
add(TreeItem item)
Inserts the TreeItem item at the right place into the tree.
|
void |
afterAdd(TreeItem item)
Is called after a TreeItem has been inserted into the tree. |
void |
afterRemove(TreeItem item)
Is called after a TreeItem has been removed from the tree. |
boolean |
allowDuplicates()
Returns true , if this tree allows elements with equal keys. |
void |
beforeAdd(TreeItem item)
Is called before a TreeItem is inserted into the tree. |
void |
beforeRemove(TreeItem item)
Is called before a TreeItem is removed from the tree. |
void |
clear()
Erases the whole tree. |
java.lang.Object |
clone()
Makes a flat clone of this object. |
java.lang.Object |
clone(java.util.Hashtable h,
int level)
clones the entire tree according to ControlledCloneable . |
Comparitor |
comparitor()
Returs the Comparitor -object that is used to compare the keys in
this tree. |
boolean |
contains(TreeItem node)
Returns true , if the TreeItem node is
part of the tree. |
TreeItem |
double_rotation(TreeItem u,
int pos1,
int pos2)
Overrides BasicTree.double_rotation(gishur.core.TreeItem, int, int) to make tree events usable for a binary search tree. |
boolean |
empty()
Returns true , if the tree is empty. |
TreeItem |
find(java.lang.Object key)
Searches for a TreeItem for which equals(key)
returns true in the whole tree. |
TreeItem |
find(java.lang.Object key,
TreeItem start)
Searches for a TreeItem whose key equals key in
the sense of the equals(Object) -method. |
TreeItem |
findBigger(java.lang.Object key)
Searches for that TreeItem in the tree, that is the
smallest of those which are bigger than key . |
TreeItem |
findBigger(java.lang.Object key,
TreeItem start)
Searches for that TreeItem in the tree, that is the
smallest of those which are bigger than key .
|
TreeItem |
findPath(java.lang.Object key)
Returns the TreeItem to which the key key would
be to attach if the order in the tree should be kept. |
TreeItem |
findSmaller(java.lang.Object key)
Searches for that TreeItem in the tree, that is the
biggest of those which are smaller than key . |
TreeItem |
findSmaller(java.lang.Object key,
TreeItem start)
Searches for that TreeItem in the tree, that is the
biggest of those which are smaller than key .
|
TreeItem |
first()
Returns the first TreeItem in the tree following the
order BasicTree.LEFT_ROOT_RIGHT_ORDER (symmetric order). |
TreeItem |
first(byte order)
Returns the first TreeItem in the tree following
the traversal order defined by order . |
int |
height()
Calculates the height of the tree. |
int |
height(TreeItem root)
Calculates the heigth of the partial tree with root root . |
java.util.Enumeration |
keys()
Creates and returns an java.util.Enumeration -object which
enumerates all keys in the tree. |
java.util.Enumeration |
keys(java.lang.Object key1,
java.lang.Object key2)
Returns an java.util.Enumeration -object which enumerates all keys
in this tree which are >= key1 and <= key2 .
|
TreeItem |
last()
Returns the last TreeItem in the tree following the
traversal order BasicTree.LEFT_ROOT_RIGHT_ORDER (symmetric order). |
TreeItem |
last(byte order)
Returns the last TreeItem in the tree following the
traversal-order defined by order . |
boolean |
leftIsSmaller()
Returns true , if smaller (or equal) keys are to be stored
in the left partial trees, false otherwise. |
int |
length()
Returns the number of stored elements in the tree. |
int |
length(TreeItem item)
Computes the number of TreeItems stored in the partial tree with
root item . |
TreeItem |
max()
Searches for the TreeItem with maximal key in the tree. |
TreeItem |
max(TreeItem start)
Searches for the biggest TreeItem in the partial tree with root
start . |
TreeItem |
min()
Searches for the TreeItem with minimal key in the tree. |
TreeItem |
min(TreeItem start)
Searches for the smallest TreeItem in the partial tree with root
start . |
TreeItem |
next(TreeItem i)
Returns the next TreeItem in the tree following
BasicTree.LEFT_ROOT_RIGHT_ORDER (symmetric order). |
TreeItem |
next(TreeItem i,
byte order)
Return the next TreeItem in the tree in traversal order
order . |
void |
onDoubleRotation(TreeItem u,
TreeItem v,
TreeItem w)
A double rotation has been performed. |
void |
onLeftRotate(TreeItem x,
TreeItem y)
A left-hand-rotation has been performed by rotating node y onto node x 's position.
|
void |
onRightRotate(TreeItem x,
TreeItem y)
A right-hand-rotation has been performed by rotating node x onto node y 's position.
|
TreeItem |
prev(TreeItem i)
Returns the previous TreeItem in symmetric order
(BasicTree.LEFT_ROOT_RIGHT_ORDER ). |
TreeItem |
prev(TreeItem i,
byte order)
Returns the previous TreeItem in the tree following
the traversal order defined by order . |
TreeItem |
remove(java.lang.Object key)
Removes the TreeItem with key key and returns it
(or null , if no such TreeItem was found). |
TreeItem |
remove(TreeItem item)
Removes TreeItem item from the tree and
returns it (or null , if the operation failed). |
boolean |
requestAccess(int accesstype,
java.lang.Object who,
java.lang.Object argument)
Object who asks his Owner for permission to
perform an operation of type accesstype with
argument argument . |
TreeItem |
root()
Returns the root-node. |
protected TreeItem |
rotation(TreeItem u,
int pos1,
int pos2)
Overrides BasicTree.rotation(gishur.core.TreeItem, int, int) to make tree events usable for a binary search tree. |
void |
setAllowDuplicates(boolean allow)
Allows or forbids the insertion of duplicate keys into this tree. |
java.util.Enumeration |
treeItems(java.lang.Object key1,
java.lang.Object key2)
Returns an java.util.Enumeration -object which enumerates all TreeItems
in this tree whose keys are >= key1 and <= key2 .
|
java.util.Enumeration |
values()
Creates and returns an java.util.Enumeration -object which
enumerates all values in the tree. |
java.util.Enumeration |
values(java.lang.Object key1,
java.lang.Object key2)
Returns an java.util.Enumeration -object which enumerates all values
in this tree whose keys are >= key1 and <= key2 .
|
Methods inherited from class gishur.core.BasicTree |
add, add, allowAccess, connect, copy, countItems, cutTree, emptyEnumeration, enumerate, enumerate, find, findLast, first, fitInPlace, getListItemChain, getRemovableTreeItem, getTreeString, last, next, ownTree, ownTree, prev, removeSym, removeTree, storeInArray, toString |
Methods inherited from class java.lang.Object |
equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait |
Constructor Detail |
public BinarySearchTree()
public BinarySearchTree(Comparitor comparitor)
Comparitor
is used to
order the tree's elements. This constructor sorts smaller keys to
the left side.comparitor
- Comparitor
-object to compare keyspublic BinarySearchTree(Comparitor comparitor, boolean left_is_smaller)
BinarySearchTree
using the Comparitor
comparitor
and the definition whether smaller keys shall be sorted to the left or to
the right side of the tree.comparitor
- Comparitor
-objekct to compare keysleft_is_smaller
- if true
, smaller keys are stored on the left
side of the tree, otherwise on the right sideMethod Detail |
public Comparitor comparitor()
Comparitor
-object that is used to compare the keys in
this tree.Comparitor
to compare keyspublic boolean allowDuplicates()
true
, if this tree allows elements with equal keys.true
, if duplicate keys are allowedpublic void setAllowDuplicates(boolean allow)
allow
- true
, if duplicate keys shall be allowed, false
otherwisepublic boolean leftIsSmaller()
true
, if smaller (or equal) keys are to be stored
in the left partial trees, false
otherwise.true
, if smaller keys are stored on the left sidepublic java.lang.Object clone()
this
object.clone
in interface Cloneable
clone
in class java.lang.Object
InternalError
- - if the Object could not be cloned properlyCloneable
public java.lang.Object clone(java.util.Hashtable h, int level)
ControlledCloneable
. That means,
all TreeItems
are cloned and connected proper.clone
in interface ControlledCloneable
clone
in class BasicTree
h
- Hashtable to indicate which objects are already clonedlevel
- indicates how deep the objects should be clonedInternalError
- - if the Object could not be cloned properlyControlledCloneable
public int length()
length
in class BasicTree
public int length(TreeItem item)
TreeItems
stored in the partial tree with
root item
.item
- the root of the partial tree to examineTreeItems
in the partial treepublic boolean empty()
true
, if the tree is empty.empty
in class BasicTree
true
, if tree is empty.public TreeItem root()
root
in class BasicTree
public int height()
public int height(TreeItem root)
root
.height
in class BasicTree
root
- the root of the partial tree to examinepublic boolean contains(TreeItem node)
true
, if the TreeItem
node
is
part of the tree. The test is performed in constant time.contains
in class BasicTree
node
- TreeItem
to search fortrue
, if node
is part of the treepublic TreeItem findPath(java.lang.Object key)
TreeItem
to which the key key
would
be to attach if the order in the tree should be kept.key
- key, whose position in the tree shall be foundTreeItem
to which key
would be to attachpublic TreeItem find(java.lang.Object key, TreeItem start)
TreeItem
whose key equals key
in
the sense of the equals(Object)
-method. The operation
takes O(n)-time in the worst case and O(log(n)) for balanced trees.
start
defines the root of the partial tree to search in.
If start==null
, the whole tree is searched.
As the Comparitor
is used for the search, it is important
that the Comparitor
of this tree is compatible to equals()
,
that means comparitor.compare(key,i)==EQUALS
only if i.equals(key)
!find
in class BasicTree
key
- the key to search forstart
- root-node of the partial tree to search inTreeItem
or null
, if no such key was foundpublic TreeItem find(java.lang.Object key)
TreeItem
for which equals(key)
returns true
in the whole tree. The complete operation takes
O(n)-time in the worst case and O(log(n))-time for balanced trees.
As the Comparitor
is used for the search, it is important
that the Comparitor
of this tree is compatible to equals()
,
that means comparitor.compare(key,i)==EQUALS
only if i.equals(key)
!key
- the key to search for in the treeTreeItem
or null
, if no such key was foundpublic TreeItem findBigger(java.lang.Object key, TreeItem start)
TreeItem
in the tree, that is the
smallest of those which are bigger than key
.
start
is the root-node of the partial tree to
search in. If start==null
, the whole tree is searched.key
- the key, for which the least bigger element shall be searchedstart
- root of the partial tree to search inTreeItem
in the tree which is >= key
public TreeItem findBigger(java.lang.Object key)
TreeItem
in the tree, that is the
smallest of those which are bigger than key
.key
- the key, for which the least bigger element shall be searchedTreeItem
in the tree which is >= key
public TreeItem findSmaller(java.lang.Object key, TreeItem start)
TreeItem
in the tree, that is the
biggest of those which are smaller than key
.
start
is the root-node of the partial tree to
search in. If start==null
, the whole tree is searched.key
- the key, for which the biggest smaller element shall be searchedstart
- root of the partial tree to search inTreeItem
of those in the tree which are <= key
public TreeItem findSmaller(java.lang.Object key)
TreeItem
in the tree, that is the
biggest of those which are smaller than key
.key
- the key, for which the biggest smaller element shall be searchedTreeItem
of those in the tree which are <= key
public TreeItem min(TreeItem start)
TreeItem
in the partial tree with root
start
. If start==null
, the whole tree is
searched.start
- root-node of the partial tree to search inTreeItem
with minimal key in the partial treepublic TreeItem min()
TreeItem
with minimal key in the tree.TreeItem
with minimal key in the treepublic TreeItem max(TreeItem start)
TreeItem
in the partial tree with root
start
. If start==null
, the whole tree is
searched.start
- root-node of the partial tree to search inTreeItem
with maximal key in the partial treepublic TreeItem max()
TreeItem
with maximal key in the tree.TreeItem
with maximal key in the treepublic TreeItem first(byte order)
TreeItem
in the tree following
the traversal order defined by order
.order
- a traversal-constant (BasicTree.ROOT_CHILDS_ORDER
, BasicTree.CHILDS_ROOT_ORDER
,
BasicTree.LEFT_ROOT_RIGHT_ORDER
, BasicTree.LEFT_RIGHT_ROOT_ORDER
or BasicTree.ROOT_LEFT_RIGHT_ORDER
)TreeItem
following order
public TreeItem first()
TreeItem
in the tree following the
order BasicTree.LEFT_ROOT_RIGHT_ORDER
(symmetric order).TreeItem
following symmetric orderpublic TreeItem last(byte order)
TreeItem
in the tree following the
traversal-order defined by order
.order
- a traversal constant (BasicTree.ROOT_CHILDS_ORDER
, BasicTree.CHILDS_ROOT_ORDER
,
BasicTree.LEFT_ROOT_RIGHT_ORDER
, BasicTree.LEFT_RIGHT_ROOT_ORDER
or BasicTree.ROOT_LEFT_RIGHT_ORDER
)TreeItem
following order
public TreeItem last()
TreeItem
in the tree following the
traversal order BasicTree.LEFT_ROOT_RIGHT_ORDER
(symmetric order).TreeItem
in symmetric orderpublic TreeItem next(TreeItem i, byte order)
TreeItem
in the tree in traversal order
order
.i
- TreeItem
whose follower shall be foundorder
- a traversal constant (BasicTree.ROOT_CHILDS_ORDER
, BasicTree.CHILDS_ROOT_ORDER
,
BasicTree.LEFT_ROOT_RIGHT_ORDER
, BasicTree.LEFT_RIGHT_ROOT_ORDER
or BasicTree.ROOT_LEFT_RIGHT_ORDER
)TreeItem
in order order
public TreeItem next(TreeItem i)
TreeItem
in the tree following
BasicTree.LEFT_ROOT_RIGHT_ORDER
(symmetric order).i
- TreeItem
whose follower shall be foundTreeItem
in symmetric orderpublic TreeItem prev(TreeItem i, byte order)
TreeItem
in the tree following
the traversal order defined by order
.i
- TreeItem
for which the previous item shall be foundorder
- a traversal constant (BasicTree.ROOT_CHILDS_ORDER
, BasicTree.CHILDS_ROOT_ORDER
,
BasicTree.LEFT_ROOT_RIGHT_ORDER
, BasicTree.LEFT_RIGHT_ROOT_ORDER
or BasicTree.ROOT_LEFT_RIGHT_ORDER
)TreeItem
in order order
public TreeItem prev(TreeItem i)
TreeItem
in symmetric order
(BasicTree.LEFT_ROOT_RIGHT_ORDER
).i
- TreeItem
for which the previous item shall be foundTreeItem
in symmtric orderpublic java.util.Enumeration keys()
java.util.Enumeration
-object which
enumerates all keys in the tree.java.util.Enumeration
-object for the keys of this treevalues()
public java.util.Enumeration values()
java.util.Enumeration
-object which
enumerates all values in the tree.java.util.Enumeration
-object for the values of this treekeys()
public java.util.Enumeration keys(java.lang.Object key1, java.lang.Object key2)
java.util.Enumeration
-object which enumerates all keys
in this tree which are >= key1
and <= key2
.
The enumeration is processed in BasicTree.LEFT_ROOT_RIGHT_ORDER
,
i.e. in ascending order, if leftIsSmaller()==true
and in
descending order otherwise.key1
- the key which defines the lower bound of the interval to enumerate or
null
, if the enumeration should start with the least keykey2
- the key which defines the upper bound of the interval to enumerate or
null
, if the enumeration should end with the biggest keyjava.util.Enumeration
-object enumerating the specified intervalpublic java.util.Enumeration values(java.lang.Object key1, java.lang.Object key2)
java.util.Enumeration
-object which enumerates all values
in this tree whose keys are >= key1
and <= key2
.
The enumeration is processed in BasicTree.LEFT_ROOT_RIGHT_ORDER
,
i.e. in ascending order, if leftIsSmaller()==true
and in
descending order otherwise.key1
- the key which defines the lower bound of the interval to enumerate or
null
, if the enumeration should start with the least keykey2
- the key which defines the upper bound of the interval to enumerate or
null
, if the enumeration should end with the biggest keyjava.util.Enumeration
-object enumerating the specified intervalpublic java.util.Enumeration treeItems(java.lang.Object key1, java.lang.Object key2)
java.util.Enumeration
-object which enumerates all TreeItems
in this tree whose keys are >= key1
and <= key2
.
The enumeration is processed in BasicTree.LEFT_ROOT_RIGHT_ORDER
,
i.e. in ascending order, if leftIsSmaller()==true
and in
descending order otherwise.key1
- the key which defines the lower bound of the interval to enumerate or
null
, if the enumeration should start with the least keykey2
- the key which defines the upper bound of the interval to enumerate or
null
, if the enumeration should end with the biggest keyjava.util.Enumeration
-object enumerating the specified intervalpublic void beforeAdd(TreeItem item)
TreeItem
is inserted into the tree.item
- TreeItem
to be insertedpublic void afterAdd(TreeItem item)
TreeItem
has been inserted into the tree.item
- inserted TreeItem
public void beforeRemove(TreeItem item)
TreeItem
is removed from the tree.item
- TreeItem
to be removedpublic void afterRemove(TreeItem item)
TreeItem
has been removed from the tree.item
- removed TreeItem
public void onLeftRotate(TreeItem x, TreeItem y)
y
onto node x
's position.
x y T1 y => x T3 T2 T3 T1 T2This event is called after the rotation took place.
x,y
- rotated TreeItems
rotation(gishur.core.TreeItem, int, int)
,
double_rotation(gishur.core.TreeItem, int, int)
public void onRightRotate(TreeItem x, TreeItem y)
x
onto node y
's position.
y x x T3 => T1 y T1 T2 T2 T3This event is called after the rotation took place.
x,y
- rotated nodesrotation(gishur.core.TreeItem, int, int)
,
double_rotation(gishur.core.TreeItem, int, int)
public void onDoubleRotation(TreeItem u, TreeItem v, TreeItem w)
TreeItems
u,v
and w
are handled as shown in the following figure:
u w v T3 => v u T1 w T1 T2 T3 T4 T2 T2This event is called after the double rotation took place.
u,v,w
- rotated nodesrotation(gishur.core.TreeItem, int, int)
,
double_rotation(gishur.core.TreeItem, int, int)
protected TreeItem rotation(TreeItem u, int pos1, int pos2)
BasicTree.rotation(gishur.core.TreeItem, int, int)
to make tree events usable for a binary search tree.rotation
in class BasicTree
BasicTree.rotation(gishur.core.TreeItem, int, int)
public TreeItem double_rotation(TreeItem u, int pos1, int pos2)
BasicTree.double_rotation(gishur.core.TreeItem, int, int)
to make tree events usable for a binary search tree.double_rotation
in class BasicTree
BasicTree.double_rotation(gishur.core.TreeItem, int, int)
protected TreeItem add_item(TreeItem item)
TreeItem
into the tree. This method is used by
all add
-methods and should be overridden in balanced trees.item
- new TreeItem
TreeItem
public TreeItem add(java.lang.Object key)
TreeItem
with key key
into the tree
at the right place.
key
should be comparable by the tree's Comparitor
to other keys
in the tree, otherwise earlier or later a CompareException
will occur.key
- key of the new TreeItem
TreeItem
containig the specified keypublic TreeItem add(java.lang.Object key, java.lang.Object value)
TreeItem
with key
and value
into the
tree at the right place.
key
should be comparable by the tree's Comparitor
to other keys
in the tree, otherwise earlier or later a CompareException
will occur.key
- the new TreeItem's
keyvalue
- the value to be storedTreeItem
with specified key and valuepublic TreeItem add(TreeItem item)
TreeItem
item
at the right place into the tree.
Only one TreeItem
will be inserted! If it is connected
to further TreeItems
, all connections to them will be cleared
by item
or a flat clone of item
will be created.item
- TreeItem
to insertTreeItem
public TreeItem remove(TreeItem item)
TreeItem
item
from the tree and
returns it (or null
, if the operation failed).{@link
- TreeItem} to be removedTreeItem
public TreeItem remove(java.lang.Object key)
TreeItem
with key key
and returns it
(or null
, if no such TreeItem
was found).key
- this key's TreeItem
shall be removedTreeItem
public void clear()
public TreeItem add(int n)
add
for int
.n
- int to be used as key for the new TreeItem
to be insertedTreeItem
containing a java.lang.Integer
wrapping n
as the keypublic TreeItem add(long n)
add
for long
.n
- long to be used as key for the new TreeItem
to be insertedTreeItem
containing a java.lang.Long
wrapping n
as the keypublic TreeItem add(float n)
add
for float
.n
- float to be used as key for the new TreeItem
to be insertedTreeItem
containing a java.lang.Float
wrapping n
as the keypublic TreeItem add(double n)
add
for double
.n
- double to be used as key for the new TreeItem
to be insertedTreeItem
containing a java.lang.Double
wrapping n
as the keypublic TreeItem add(boolean n)
add
for boolean
.n
- boolean to be used as key for the new TreeItem
to be insertedTreeItem
containing a java.lang.Boolean
wrapping n
as the keypublic boolean requestAccess(int accesstype, java.lang.Object who, java.lang.Object argument)
who
asks his Owner
for permission to
perform an operation of type accesstype
with
argument argument
. This method overrides the
BasicTree.requestAccess(int, java.lang.Object, java.lang.Object)
-method to make it more restrictive
(the key and the maximal rank must not be changed).requestAccess
in class BasicTree
accesstype
- type of action (i.e. type of required access)who
- object asking his Owner
for permissionargument
- argument of the requested operationtrue
, if the Owner
allows the operation, false
otherwise
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |