grafalgo::SaBstSet Class Reference

Class representing a collection of self-adjusting binary search trees. More...

#include <SaBstSet.h>

Inheritance diagram for grafalgo::SaBstSet:

Collaboration diagram for grafalgo::SaBstSet:

List of all members.

Public Member Functions
	SaBstSet (int=100)
	Constructor for SaBstSet class.
	~SaBstSet ()
	Destructor for SaBstSet class.
bst	find (index)
	Get the root of the bst containing an item.
index	access (keytyp, bst &)
	Get the item with a specified key value.
bool	insert (index, bst &)
	Insert item into a bst.
void	remove (index, bst &)
	Remove an item from a bst.
BstPair	split (index, bst)
	Divide a bst at an item.
Protected Member Functions
index	splay (index)
	Splay a search tree.
void	splaystep (index)
	Perform a single splay step.

---

Detailed Description

Class representing a collection of self-adjusting binary search trees.

Each BST represents a set of items, where each item is represented by a tree node.

Definition at line 20 of file SaBstSet.h.

---

Constructor & Destructor Documentation

grafalgo::SaBstSet::SaBstSet

(

int

size = 100

)

Constructor for SaBstSet class.

Parameters:

size	defines the index range for the constructed object.

Definition at line 20 of file SaBstSet.cpp.

grafalgo::SaBstSet::~SaBstSet

(

)

Destructor for SaBstSet class.

Definition at line 23 of file SaBstSet.cpp.

---

Member Function Documentation

index grafalgo::SaBstSet::access	(	keytyp	k,
		bst &	t
	)

Get the item with a specified key value.

Parameters:

k	is a key value
t	is a reference to the root of some bst; if the operation changes the root, then t will change

Returns:

the item in the tree with the specified key, or 0 if no item has that key

Definition at line 65 of file SaBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

bst grafalgo::SaBstSet::find

(

index

i

)

Get the root of the bst containing an item.

Parameters:

i	is an item in some bst

Returns:

the caonical element of the bst containing i; note that the operation restructures the tree possibly changing the root

Definition at line 56 of file SaBstSet.cpp.

Here is the call graph for this function:

bool grafalgo::SaBstSet::insert	(	index	i,
		bst &	t
	)

Insert item into a bst.

Parameters:

i	is a singleton item
t	is the root of the bst that i is to be inserted into; if the operation changes the root, t is changed

Returns:

true on success, false on failure

Reimplemented from grafalgo::BstSet.

Definition at line 83 of file SaBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::SaBstSet::remove	(	index	i,
		bst &	t
	)

Remove an item from a bst.

Parameters:

i	is an item in some bst
t	is the bst containing i

Returns:

the root of the bst that results from removing i from t

Reimplemented from grafalgo::BstSet.

Definition at line 105 of file SaBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

index grafalgo::SaBstSet::splay

(

index

x

)

[protected]

Splay a search tree.

Parameters:

x	is an item in a bst (equivalently, node in a search tree); the operation restructures the tree, moving x to the root

Returns:

the root of the bst following the restructuring

Definition at line 30 of file SaBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

void grafalgo::SaBstSet::splaystep

(

index

x

)

[protected]

Perform a single splay step.

Parameters:

x	is a node in a search tree

Definition at line 38 of file SaBstSet.cpp.

Here is the call graph for this function:

Here is the caller graph for this function:

BstSet::BstPair grafalgo::SaBstSet::split	(	index	i,
		bst	t
	)

Divide a bst at an item.

Parameters:

i	is the index of a node in some bst
t	is the root of the bst containing i

Returns:

the pair of bst [t1,t2] that results from splitting s into three parts; t1 (containing ityems with keys smaller than that of i), i itself, and t2 (contining items with keys larger than that of i)

Reimplemented from grafalgo::BstSet.

Reimplemented in grafalgo::DkBstSet.

Definition at line 132 of file SaBstSet.cpp.

Here is the call graph for this function:

---

The documentation for this class was generated from the following files:

• /Users/jst/src/grafalgo/cpp/include/SaBstSet.h
• /Users/jst/src/grafalgo/cpp/dataStructures/searchTrees/SaBstSet.cpp