asd_library.tree.bstree
Class BSTree

java.lang.Object
  |
  +--asd_library.tree.bstree.BSTree
All Implemented Interfaces:
Dictionary_adt

public class BSTree
extends java.lang.Object
implements Dictionary_adt

The class BSTree implements a binary tree with the following property: for each node n, every left-subtree value is less then the key value v stored in n and every right-subtree value is greater then v.


Field Summary
protected  BSTNode root
           
protected  int size
           
 
Constructor Summary
BSTree()
          Creates an empty BSTree
 
Method Summary
 void balance(java.lang.Comparable[] data, int first, int last)
          Inserts the element from the specified array into this tree.
 void breadthFirst()
          Implements a breadth-first traversal from the root towards the leafs and from left towards right.
 void clear()
          Removes all of the elements from this BSTree
 java.lang.Comparable element(BSTNode v)
          Method to get element field.
 java.lang.Object find(java.lang.Comparable el)
          Finds the specified element el.
 int getSize()
          Returns the number of nodes in this BSTree.
 void inorder()
          Implements a inorder traversal of this BSTree, beginning from the root.
 void inorder(BSTNode p)
          Recorsive method to implement the inorder traversal, beginning from the specified node p.
 BSTNode insert(BSTNode node)
          Inserts the specified node in this BSTree.
 java.lang.Object insert(java.lang.Comparable el)
          Inserts the specified element in this BSTree.
 boolean isEmpty()
          Tests if this BSTree has no components.
 boolean isInTree(java.lang.Comparable el)
          Tests if the specified object is in this BSTree.
 boolean isLeaf(BSTNode v)
          Verifies if the node v is a leaf.
 boolean isRoot(BSTNode v)
          Verifies if the node v is the root of this tree
 void iterativeInorder()
          Iterative method to implement the inorder traversal.
 void iterativePostorder()
          Iterative method to implement the postorder traversal.
 void iterativePreorder()
          Iterative method to implement the preorder traversal.
 BSTNode iterativeSearch(BSTNode p, java.lang.Comparable el)
          Iterative method to find the element el, starting from the specified node p
 BSTNode iterativeSearch(java.lang.Comparable el)
          Searches for the element el in this BSTree.
 BSTNode leftChild(BSTNode v)
          Returns the left child node of v
 void postorder()
          Implements a postorder traversal of this BSTree, beginning from the root.
 void postorder(BSTNode p)
          Recorsive method to implement the postorder traversal, beginning from the specified node p.
 BSTNode predecessor(BSTNode p, java.lang.Comparable el)
          Searches the predecessor of the node with key equals to el, starting from the node p
 BSTNode predecessor(java.lang.Comparable el)
          Searches the predecessor of the node with key equals to el.
 void preorder()
          Implements a preorder traversal of this BSTree, beginning from the root.
 void preorder(BSTNode p)
          Recorsive method to implement the preorder traversal, beginning from the specified node p.
 java.lang.Comparable remove(java.lang.Comparable el)
          Removes the element el from this tree
 BSTNode rightChild(BSTNode v)
          Returns the right child node of v
 BSTNode root()
          Return the BSTree root node
 BSTNode search(BSTNode p, java.lang.Comparable el)
          Recorsive method to find the element el, starting from the specified node p
 BSTNode search(java.lang.Comparable el)
          Searches for the element el in this BSTree.
 BSTNode successor(BSTNode p, java.lang.Comparable el)
          Searches the successor of the node with key equals to el, starting from the node p
 BSTNode successor(java.lang.Comparable el)
          Searches the successor of the node with key equals to el.
 int treeHeight()
          Returns the height of this BSTree.
 int treeHeight(BSTNode node)
          Returns the height of the subtree with root in node.
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Field Detail

root

protected BSTNode root

size

protected int size
Constructor Detail

BSTree

public BSTree()
Creates an empty BSTree

Method Detail

root

public BSTNode root()
Return the BSTree root node

Returns:
the BSTNode that contains the tree root.

element

public java.lang.Comparable element(BSTNode v)
Method to get element field.

Parameters:
v - the node.
Returns:
the element field or null if t is null.

isLeaf

public boolean isLeaf(BSTNode v)
Verifies if the node v is a leaf.

Parameters:
v - the node
Returns:
true if v is a leaf, false otherwise.

isRoot

public boolean isRoot(BSTNode v)
Verifies if the node v is the root of this tree

Parameters:
v - the node
Returns:
true if the node v is root, false otherwise.

insert

public java.lang.Object insert(java.lang.Comparable el)
Inserts the specified element in this BSTree.

Specified by:
insert in interface Dictionary_adt
Parameters:
el - element to insert.
Returns:
the object that represents the inserted node.

remove

public java.lang.Comparable remove(java.lang.Comparable el)
Removes the element el from this tree

Specified by:
remove in interface Dictionary_adt
Parameters:
el - the elment to remove
Returns:
the element el if it was in the tree, null otherwise.

find

public java.lang.Object find(java.lang.Comparable el)
Finds the specified element el.

Specified by:
find in interface Dictionary_adt
Parameters:
el - the element to search.
Returns:
the node that contains the specified element el.

leftChild

public BSTNode leftChild(BSTNode v)
Returns the left child node of v

Parameters:
v - the parent node
Returns:
the left child node

rightChild

public BSTNode rightChild(BSTNode v)
Returns the right child node of v

Parameters:
v - the parent node
Returns:
the right child node

clear

public void clear()
Removes all of the elements from this BSTree


isEmpty

public boolean isEmpty()
Tests if this BSTree has no components.

Returns:
true if and only if this BSTree has no components, that is, its size is zero; false otherwise

search

public BSTNode search(java.lang.Comparable el)
Searches for the element el in this BSTree.

Parameters:
el - the element to search for.
Returns:
the node that contains el, if any exists; null otherwise.

search

public BSTNode search(BSTNode p,
                      java.lang.Comparable el)
Recorsive method to find the element el, starting from the specified node p

Parameters:
p - the node to start searching from.
el - the element.
Returns:
the node that contains el, if any exists; null otherwise.

iterativeSearch

public BSTNode iterativeSearch(java.lang.Comparable el)
Searches for the element el in this BSTree.

Parameters:
el - the element to search for.
Returns:
the node that contains el, if any exists; null otherwise.

iterativeSearch

public BSTNode iterativeSearch(BSTNode p,
                               java.lang.Comparable el)
Iterative method to find the element el, starting from the specified node p

Parameters:
p - the node to start searching from.
el - the element.
Returns:
the node that contains el, if any exists; null otherwise.

insert

public BSTNode insert(BSTNode node)
Inserts the specified node in this BSTree.

Parameters:
node - node to insert.
Returns:
the inserted node.

isInTree

public boolean isInTree(java.lang.Comparable el)
Tests if the specified object is in this BSTree.

Parameters:
el - the object to test.
Returns:
true if and only if the specified object is in this BSTree; false otherwise.

getSize

public int getSize()
Returns the number of nodes in this BSTree.

Returns:
the number of nodes in this BSTree.

preorder

public void preorder()
Implements a preorder traversal of this BSTree, beginning from the root. Calls the recorsive method preorder(BSTNode p)


inorder

public void inorder()
Implements a inorder traversal of this BSTree, beginning from the root. Calls the recorsive method inorder(BSTNode p).


postorder

public void postorder()
Implements a postorder traversal of this BSTree, beginning from the root. Calls the recorsive method postorder(BSTNode p)


inorder

public void inorder(BSTNode p)
Recorsive method to implement the inorder traversal, beginning from the specified node p.

Parameters:
p - a node.

preorder

public void preorder(BSTNode p)
Recorsive method to implement the preorder traversal, beginning from the specified node p.

Parameters:
p - a node.

postorder

public void postorder(BSTNode p)
Recorsive method to implement the postorder traversal, beginning from the specified node p.

Parameters:
p - a node.

iterativePreorder

public void iterativePreorder()
Iterative method to implement the preorder traversal.


iterativeInorder

public void iterativeInorder()
Iterative method to implement the inorder traversal.


iterativePostorder

public void iterativePostorder()
Iterative method to implement the postorder traversal.


breadthFirst

public void breadthFirst()
Implements a breadth-first traversal from the root towards the leafs and from left towards right.


treeHeight

public int treeHeight()
Returns the height of this BSTree. Calls the recorsive method treeHeight (BSTNode node).

Returns:
the height of this BSTree

treeHeight

public int treeHeight(BSTNode node)
Returns the height of the subtree with root in node.

Parameters:
node - a node.
Returns:
the height of the subtree with the specified node as root.

predecessor

public BSTNode predecessor(java.lang.Comparable el)
Searches the predecessor of the node with key equals to el.

Parameters:
el - the specified element.
Returns:
the predecessor node.

predecessor

public BSTNode predecessor(BSTNode p,
                           java.lang.Comparable el)
Searches the predecessor of the node with key equals to el, starting from the node p

Parameters:
p - the specified node
el - key of the specified node.
Returns:
the predecessor node of el.

successor

public BSTNode successor(java.lang.Comparable el)
Searches the successor of the node with key equals to el.

Parameters:
el - the specified element.
Returns:
the successor node.

successor

public BSTNode successor(BSTNode p,
                         java.lang.Comparable el)
Searches the successor of the node with key equals to el, starting from the node p

Parameters:
p - the specified node
el - key of the specified node.
Returns:
the successor node of el.

balance

public void balance(java.lang.Comparable[] data,
                    int first,
                    int last)
Inserts the element from the specified array into this tree.

Parameters:
data - array of elements.
first - first index in the array.
last - index in the array.