AVLTree< K, V > Class Template Reference

The AVLTree class represents a templated linked-memory tree data structure. More...

#include <avltree.h>

Classes
struct	Node
	Represents a tree node; that is, an element in a AVLTree. More...

Public Member Functions
	AVLTree ()
	Constructor to create an empty tree.
	AVLTree (const AVLTree &other)
	Copy constructor.
	~AVLTree ()
	Destructor; frees all nodes associated by this tree.
const AVLTree &	operator= (const AVLTree &rhs)
	Assignment operator. More...
void	clear ()
	Frees all nodes associated with this tree and sets it to be empty.
void	insert (const K &key, const V &value)
	Inserts into the AVLTree. More...
V	find (const K &key) const
	Finds an element in the AVL tree. More...
void	print (ostream &out=cout) const
	Prints the AVLTree to a stream (default stdout). More...
void	setOutput (ostream &newOut)
	This is a function used for grading. More...

Private Member Functions
void	insert (Node *&node, const K &key, const V &value)
	Private helper function for the public insert function. More...
V	find (Node *node, const K &key) const
	Finds an element in the AVL tree. More...
void	rotateRight (Node *&node)
	Rotates the tree right (there is an imbalance on the left side).
void	rotateLeft (Node *&node)
	Rotates the tree left (there is an imbalance on the right side).
void	rotateRightLeft (Node *&node)
	A right left rotation. More...
void	rotateLeftRight (Node *&node)
	A left right rotation. More...
int	heightOrNeg1 (const Node *node) const
Node *	copy (const Node *subRoot)
	Helper function for operator= and cctor. More...
void	clear (Node *subRoot)
	Private helper function for clear that clears beneath the parameter node. More...

Private Attributes
ostream *	_out
	member variable used for grading

Detailed Description

template<class K, class V>
class AVLTree< K, V >

The AVLTree class represents a templated linked-memory tree data structure.

Member Function Documentation

template<class K , class V >

const AVLTree< K, V > & AVLTree< K, V >::operator=

(

const AVLTree< K, V > &

rhs

)

Assignment operator.

Parameters

rhs	The tree to make a copy of

Returns

A reference to the current tree

template<class K , class V >

void AVLTree< K, V >::insert	(	const K &	key,
		const V &	value
	)

Inserts into the AVLTree.

Parameters

key	The key to insert
value	The value for the key to insert

template<class K , class V >

V AVLTree< K, V >::find

(

const K &

key

)

const

Finds an element in the AVL tree.

Parameters

key	The element to search for

Returns

the value stored for that key

template<class K , class V >

void AVLTree< K, V >::print

(

ostream &

out = cout

)

const

Prints the AVLTree to a stream (default stdout).

Parameters

out	The stream to print to

template<class K , class V >

void AVLTree< K, V >::setOutput

(

ostream &

newOut

)

This is a function used for grading.

Parameters

newOut

The stream to print to.

template<class K , class V >

void AVLTree< K, V >::insert ( Node *&  node, const K &  key, const V &  value  )

private

Private helper function for the public insert function.

Parameters

node	The current node in the recursion
key	The key to insert
value	The value for the key to insert

template<class K , class V >

V AVLTree< K, V >::find ( Node *  node, const K &  key  ) const

private

Finds an element in the AVL tree.

Parameters

node	The node to search from (current subroot)
key	The element to search for

Returns

the value stored for that key

template<class K , class V >

void AVLTree< K, V >::rotateRightLeft ( Node *&  node )

private

A right left rotation.

This function should simply call rotateRight and rotateLeft.

template<class K , class V >

void AVLTree< K, V >::rotateLeftRight ( Node *&  node )

private

A left right rotation.

This function should simply call rotateLeft and rotateRight.

Parameters

node	The node to rotate

template<class K , class V >

int AVLTree< K, V >::heightOrNeg1 ( const Node *  node ) const

private

Parameters

node	The node's height to check

Returns

the height of the node if it's non-NULL or -1 if it is NULL

template<class K , class V >

AVLTree< K, V >::Node * AVLTree< K, V >::copy ( const Node *  subRoot )

private

Helper function for operator= and cctor.

Parameters

subRoot

The current node in the recursion

template<class K , class V >

void AVLTree< K, V >::clear ( Node *  subRoot )

private

Private helper function for clear that clears beneath the parameter node.

Parameters

subRoot

The current node in the recursion

---

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

• avltree.h
• avltree.cpp
• avltree_given.cpp