lab_avl
AVL Apocalypse
AVLTree< K, V > Class Template Reference

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 AVLTreeoperator= (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...
 
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...
 
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...
 
Nodecopy (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

Noderoot
 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
Kthe type of key stored in the tree
Vthe 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
otherThe 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
rhsThe 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
keyThe key to insert
valueThe 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
keyThe 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
keyThe 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
outThe 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
newOutThe 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
nodeThe current node in the recursion
keyThe key to insert
valueThe 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
nodeThe current node in the recursion
keyThe 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
nodeThe node to search from (current subroot)
keyThe 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
nodeThe 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
nodeThe 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
nodeThe 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
nodeThe 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
nodeThe node to balance.

◆ heightOrNeg1()

template<class K , class V >
int AVLTree< K, V >::heightOrNeg1 ( const Node node) const
private
Parameters
nodeThe 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
firstThe first node to swap
secondThe 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
subRootThe 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
subRootThe 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: