The AVLTree class represents a linked-memory AVL Tree. More...

#include "avltree.h"

Collaboration diagram for AVLTree< K, V >:

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

Public Member Functions
	AVLTree ()
	Constructor to create an empty tree. More...

	AVLTree (const AVLTree &other)
	Copy constructor. More...

	~AVLTree ()
	Destructor; frees all nodes associated with this tree. More...

const AVLTree &	operator= (const AVLTree &rhs)
	Assignment operator. More...

void	clear ()
	Frees all nodes associated with this tree and sets it to be empty. More...

void	insert (const K &key, const V &value)
	Inserts a key and value into the AVLTree. More...

void	remove (const K &key)
	Removes a key from 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. More...

void	setOutput (ostream &newOut)
	This function is 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...

void	remove (Node *&node, const K &key)
	Private helper function for the public remove function. More...

V	find (Node *node, const K &key) const
	Finds a value (by key) in the AVL tree. More...

void	rotateRight (Node *&node)
	Rotate the tree right (there is an imbalance on the left side). More...

void	rotateLeft (Node *&node)
	Rotates the tree left (there is an imbalance on the right side). More...

void	rotateRightLeft (Node *&node)
	A right-left rotation. More...

void	rotateLeftRight (Node *&node)
	A left-right rotation. More...

void	rebalance (Node *&node)
	Rebalance a node by performing rotations. More...

int	heightOrNeg1 (const Node *node) const

void	swap (Node &first, Node &second)
	Swap the keys and values of two nodes. More...

Node *	copy (const Node *subRoot)
	Helper function for operator= and AVLTree(const AVLTree &). More...

void	clear (Node *subRoot)
	Private helper function for clear that clears beneath the parameter node. More...

Private Attributes
Node *	root
	The root of the tree. More...

ostream *	_out
	This variable is used for grading. More...

Detailed Description

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

The AVLTree class represents a linked-memory AVL Tree.

Template Parameters

K	the type of key stored in the tree
V	the type of value stored in the tree

Constructor & Destructor Documentation

◆ AVLTree() [1/2]

template<class K , class V >

AVLTree< K, V >::AVLTree ( )

Constructor to create an empty tree.

◆ AVLTree() [2/2]

template<class K , class V >

AVLTree< K, V >::AVLTree ( const AVLTree< K, V > & other )

Copy constructor.

Parameters

other The tree to copy

◆ ~AVLTree()

template<class K , class V >

AVLTree< K, V >::~AVLTree ( )

Destructor; frees all nodes associated with this tree.

Member Function Documentation

◆ operator=()

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 copy

Returns: A reference to the current tree

◆ clear() [1/2]

template<class K , class V >

void AVLTree< K, V >::clear ( )

Frees all nodes associated with this tree and sets it to be empty.

◆ insert() [1/2]

template<class K , class V >

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

Inserts a key and value into the AVLTree.

Parameters

key	The key to insert
value	The value associated with the key

◆ remove() [1/2]

template<class K , class V >

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

Removes a key from the AVLTree.

The key is assumed to exist in the tree.

Parameters

key	The key to remove

◆ find() [1/2]

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

◆ print()

template<class K , class V >

void AVLTree< K, V >::print ( ostream & out = cout ) const

Prints the AVLTree to a stream.

Parameters

out	The stream to print to (default is stdout)

◆ setOutput()

template<class K , class V >

void AVLTree< K, V >::setOutput ( ostream & newOut )

This function is used for grading.

Parameters

newOut The stream to print to

◆ insert() [2/2]

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 associated with the key

◆ remove() [2/2]

template<class K , class V >

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

private

Private helper function for the public remove function.

Parameters

node	The current node in the recursion
key	The key to remove

◆ find() [2/2]

template<class K , class V >

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

private

Finds a value (by key) in the AVL tree.

Parameters

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

Returns: The value stored for that key

◆ rotateRight()

template<class K , class V >

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

private

Rotate the tree right (there is an imbalance on the left side).

Parameters

node	The node to rotate

◆ rotateLeft()

template<class K , class V >

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

private

Rotates the tree left (there is an imbalance on the right side).

Parameters

node	The node to rotate

◆ rotateRightLeft()

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.

Parameters

node	The node to rotate

◆ rotateLeftRight()

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

◆ rebalance()

template<class K , class V >

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

private

Rebalance a node by performing rotations.

You can assume that node->left and node->right are both balanced. Even if no rotations are required, you should update the node's height.

Parameters

node	The node to balance.

◆ heightOrNeg1()

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

◆ swap()

template<class K , class V >

void AVLTree< K, V >::swap	(	Node *&	first,
		Node *&	second
	)

private

Swap the keys and values of two nodes.

Parameters

first	The first node to swap
second	The node to swap with

◆ copy()

template<class K , class V >

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

private

Helper function for operator= and AVLTree(const AVLTree &).

Parameters

subRoot The current node in the recursion

◆ clear() [2/2]

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

Member Data Documentation

◆ root

template<class K , class V >

Node* AVLTree< K, V >::root

private

The root of the tree.

◆ _out

template<class K , class V >

ostream* AVLTree< K, V >::_out

private

This variable is used for grading.

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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ AVLTree() [1/2]

◆ AVLTree() [2/2]

◆ ~AVLTree()

Member Function Documentation

◆ operator=()

◆ clear() [1/2]

◆ insert() [1/2]

◆ remove() [1/2]

◆ find() [1/2]

◆ print()

◆ setOutput()

◆ insert() [2/2]

◆ remove() [2/2]

◆ find() [2/2]

◆ rotateRight()

◆ rotateLeft()

◆ rotateRightLeft()

◆ rotateLeftRight()

◆ rebalance()

◆ heightOrNeg1()

◆ swap()

◆ copy()

◆ clear() [2/2]

Member Data Documentation

◆ root

◆ _out

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