You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
87 lines
3.3 KiB
C++
87 lines
3.3 KiB
C++
AvlTree.h - Header file for AVL tree
|
|
|
|
#ifndef AVL_TREE_H_
|
|
#define AVL_TREE_H_
|
|
|
|
|
|
// Node and forward declaration because g++ does
|
|
// not understand nested classes.
|
|
template <class Comparable>
|
|
class AvlTree;
|
|
|
|
template <class Comparable>
|
|
class AvlNode
|
|
{
|
|
Comparable element;
|
|
AvlNode *left;
|
|
AvlNode *right;
|
|
int height;
|
|
|
|
AvlNode( const Comparable & theElement, AvlNode *lt, AvlNode *rt, int h = 0 )
|
|
: element( theElement ), left( lt ), right( rt ), height( h ) { }
|
|
friend class AvlTree<Comparable>;
|
|
};
|
|
|
|
#include "dsexceptions.h"
|
|
#include <iostream.h> // For NULL
|
|
|
|
// AvlTree class
|
|
//
|
|
// CONSTRUCTION: with ITEM_NOT_FOUND object used to signal failed finds
|
|
//
|
|
// ******************PUBLIC OPERATIONS*********************
|
|
// void insert( x ) --> Insert x
|
|
// void remove( x ) --> Remove x (unimplemented)
|
|
// Comparable find( x ) --> Return item that matches x
|
|
// Comparable findMin( ) --> Return smallest item
|
|
// Comparable findMax( ) --> Return largest item
|
|
// boolean isEmpty( ) --> Return true if empty; else false
|
|
// void makeEmpty( ) --> Remove all items
|
|
// void printTree( ) --> Print tree in sorted order
|
|
|
|
template <class Comparable>
|
|
class AvlTree
|
|
{
|
|
public:
|
|
explicit AvlTree( const Comparable & notFound );
|
|
AvlTree( const AvlTree & rhs );
|
|
~AvlTree( );
|
|
|
|
const Comparable & findMin( ) const;
|
|
const Comparable & findMax( ) const;
|
|
const Comparable & find( const Comparable & x ) const;
|
|
bool isEmpty( ) const;
|
|
void printTree( ) const;
|
|
|
|
void makeEmpty( );
|
|
void insert( const Comparable & x );
|
|
void remove( const Comparable & x );
|
|
|
|
const AvlTree & operator=( const AvlTree & rhs );
|
|
|
|
private:
|
|
AvlNode<Comparable> *root;
|
|
const Comparable ITEM_NOT_FOUND;
|
|
|
|
const Comparable & elementAt( AvlNode<Comparable> *t ) const;
|
|
|
|
void insert( const Comparable & x, AvlNode<Comparable> * & t ) const;
|
|
AvlNode<Comparable> * findMin( AvlNode<Comparable> *t ) const;
|
|
AvlNode<Comparable> * findMax( AvlNode<Comparable> *t ) const;
|
|
AvlNode<Comparable> * find( const Comparable & x, AvlNode<Comparable> *t ) const;
|
|
void makeEmpty( AvlNode<Comparable> * & t ) const;
|
|
void printTree( AvlNode<Comparable> *t ) const;
|
|
AvlNode<Comparable> * clone( AvlNode<Comparable> *t ) const;
|
|
|
|
// Avl manipulations
|
|
int height( AvlNode<Comparable> *t ) const;
|
|
int max( int lhs, int rhs ) const;
|
|
void rotateWithLeftChild( AvlNode<Comparable> * & k2 ) const;
|
|
void rotateWithRightChild( AvlNode<Comparable> * & k1 ) const;
|
|
void doubleWithLeftChild( AvlNode<Comparable> * & k3 ) const;
|
|
void doubleWithRightChild( AvlNode<Comparable> * & k1 ) const;
|
|
};
|
|
|
|
#include "AvlTree.cpp"
|
|
#endif
|