AVLTree

http://www.staroceans.com/AVLTree.htm

A. First Edition

This is first edition of my AVL Tree and I never expect it takes so long as almost one week to finish! Of course

it is partly because of Christmas when I was continually interrupt by the earthly issues such as visiting a 

friend and wasting some meaningful time on meaningless matters. 

B.The problem

To write AVL tree on template basis and try to keep as much as possible of original BST frame work

because the code by Mr. Shaffer is very concise and compact! And efficiency is also a very important

issue here. As AVLTree has to store extra information than a BST, it is expected that we need to 

reduce as many "balancing operations" as possible. 

By adding a little piece of code in "insert" method of BST, I actually try to do the keeping-balance

job along the "insert" operation from bottom-up which always keep each node up-to-date balanced. It

is believed by me the best solution to implement it. Unfortunately I have to keep the clue of the

path which leads to the newly-inserted node at leaf position. So, I was obliged to add one more

field in node---"inLeft" which is a boolean value indicating which side the path goes down to the

new leaf. Along with it is the "height" data which is the absolute height of a subtree rooted as

current node. I thought it is a cheating in pseudo code by using "balancing-factor" as instead of

using "real height" of each node. But after finishing the program with several big changes, I

realized I might do some stupid things on assuming that absolute height is necessary. Maybe in

second edition I should combine both "inLeft" and "height" together with "factor"----balancing

factor.

D.The major functions

1. bool insert(const Elem& e)

Do you expect that I might start from here? But no, I didn't change anything here. And it is only 

after I finished, I thought I can omit it even "inserthelp" is not virtual.

2. BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);

This function is almost same as original BST except I try to update the height after each insertion

which will go up from the inserted new leaf along path. And before that insertion, I placed a road

sign "inLeaf" to indicate which side the path takes.

3. void updateHeight(BinNode<Elem>*& subroot);

This is the key part of program where you update height first and then try to examine the balance

and try to keep it. It is the tricky part as I change the code many times. Finally I realized that

there are two big cases: a) The first root which is also the first node with factor 2/-2; b) The node

whose son node has factor of 2/-2; There are some extra conditions to examine the "first" in a) to 

make sure it is the "first". 

4. int getTreeHeight(BinNode<Elem>* subroot);

I resist to use recursive method because the field "height" is a short-cut.

5. BinNode<Elem>* singleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);

Don't forget to adjust balance after rotating and the sequence is important as you have to do it from

bottom-up.

6. BinNode<Elem>* doubleRotate(BinNode<Elem>* parent, bool isRoot, bool left2right);

I made it look simple by adding the "doDouble" and quite satisfy with it.

E.Further improvement

F.File listing

1. AVLTree.h

2. BinNode.h

3. BST.h

4. dictionary.h

5. Elem.h

6. AVLTree.cpp  (main)

file name: BinNode.h

// Binary tree node abstract class

template <class Elem> class BinNode {

public:

	// Return the node's element

	virtual Elem& val() = 0;

	// Set the node's element

	virtual void setVal(const Elem&) = 0;

	// Return the node's left child

	virtual BinNode* left() const = 0;

	// Set the node's left child

	virtual void setLeft(BinNode*) = 0;

	// Return the node's right child

	virtual BinNode* right() const = 0;

	// Set the node's right child

	virtual void setRight(BinNode*) = 0;

	// Return true iff the node is a leaf

	virtual bool isLeaf() = 0;

	//my personal preference

	virtual BinNode<Elem>* getSon(bool isLeft)const=0; 

	//my personal preference

	virtual void setSon(BinNode<Elem>* son, bool isLeft)=0;

};



// Binary tree node class

template <class Elem>

class BinNodePtr : public BinNode<Elem> {

private:

	Elem it;                     // The node's value

	BinNodePtr* lc;              // Pointer to left child

	BinNodePtr* rc;              // Pointer to right child

public:

	// Two constructors -- with and without initial values

	BinNodePtr() { lc = rc = NULL; }

	BinNodePtr(Elem e, BinNodePtr* l =NULL,

					 BinNodePtr* r =NULL)

	{ it = e; lc = l; rc = r; }

	~BinNodePtr() {}             // Destructor

	Elem& val() { return it; }

	void setVal(const Elem& e) { it = e; }

	inline BinNode<Elem>* left() const { return lc; }

	void setLeft(BinNode<Elem>* b) { lc = (BinNodePtr*)b; }

	inline BinNode<Elem>* right() const { return rc; }

	void setRight(BinNode<Elem>* b) { rc = (BinNodePtr*)b; }

	bool isLeaf() { return (lc == NULL) && (rc == NULL); }

	BinNode<Elem>* getSon(bool isLeft)const {return isLeft?lc:rc;}

	void setSon(BinNode<Elem>* son, bool isLeft)

	{

		isLeft?setLeft(son):setRight(son);

	}

};





template <class Elem>

class AVLNodePtr : public BinNode<Elem> 

{

protected:

	Elem it;                     // The node's value

	AVLNodePtr* lc;              // Pointer to left child

	AVLNodePtr* rc;              // Pointer to right child

	int height;

	bool inLeft;

public:

 // Two constructors -- with and without initial values

	AVLNodePtr() { lc = rc = NULL; height=1; inLeft=true; }

	AVLNodePtr(Elem e, AVLNodePtr<Elem>* l =NULL,

					 AVLNodePtr<Elem>* r =NULL, int newHeight=1)

	{ it = e; lc = l; rc = r; height=newHeight; inLeft=true;}

	~AVLNodePtr() {}             // Destructor

	Elem& val() { return it; }

	void setVal(const Elem& e) { it = e; }

	BinNode<Elem>* left() const { return lc; }

	void setLeft(BinNode<Elem>* b) { lc = (AVLNodePtr*)b; }

	inline BinNode<Elem>* right() const { return rc; }

	void setRight(BinNode<Elem>* b) { rc = (AVLNodePtr*)b; }

	bool isLeaf() { return (lc == NULL) && (rc == NULL); }

	void setHeight(int newHeight){height=newHeight;}

	int getHeight(){return height;}

	BinNode<Elem>* getSon(bool isLeft)const {return isLeft?lc:rc;}

	bool getSide() const {return inLeft;}

	void setSide(bool isLeft){ inLeft=isLeft;}

	void setSon(BinNode<Elem>* son, bool isLeft)

	{

		isLeft?setLeft(son):setRight(son);

	}



};

file name: BST.h

// This file includes all of the pieces of the BST implementation



#include "dictionary.h"



#include "binnode.h"



// Binary Search Tree implementation for the Dictionary ADT

template <class Key, class Elem, class KEComp, class EEComp>

class BST : public Dictionary<Key, Elem, KEComp, EEComp> {

protected:

  BinNode<Elem>* root;   // Root of the BST

  int nodecount;         // Number of nodes in the BST

  // Private "helper" functions

  void clearhelp(BinNode<Elem>*);

  BinNode<Elem>* inserthelp(BinNode<Elem>*, const Elem&);

  BinNode<Elem>* deletemin(BinNode<Elem>*, BinNode<Elem>*&);

  BinNode<Elem>* removehelp(BinNode<Elem>*, const Key&,

                            BinNode<Elem>*&);

  bool findhelp(BinNode<Elem>*, const Key&, Elem&) const;

  void printhelp(BinNode<Elem>*, int) const;

public:

  BST() { root = NULL; nodecount = 0; }  // Constructor

  ~BST() { clearhelp(root); }            // Destructor

  void clear()

    { clearhelp(root); root = NULL; nodecount = 0; }

  bool insert(const Elem& e) {

    root = inserthelp(root, e);

    nodecount++;

    return true;

  }

  bool remove(const Key& K, Elem& e) {

    BinNode<Elem>* t = NULL;

    root = removehelp(root, K, t);

    if (t == NULL) return false;  // Nothing found

    e = t->val();

    nodecount--;

    delete t;

    return true;

  }

  bool removeAny(Elem& e) { // Delete min value

    if (root == NULL) return false; // Empty tree

    BinNode<Elem>* t;

    root = deletemin(root, t);

    e = t->val();

    delete t;

    nodecount--;

    return true;

  }

  bool find(const Key& K, Elem& e) const

    { return findhelp(root, K, e); }

  int size() { return nodecount; }

  void print() const {

    if (root == NULL) cout << "The BST is empty.\n";

    else printhelp(root, 0);

  }

};



template <class Key, class Elem, class KEComp, class EEComp>

void BST<Key, Elem, KEComp, EEComp>::

clearhelp(BinNode<Elem>* subroot) {

  if (subroot == NULL) return;

  clearhelp(subroot->left());

  clearhelp(subroot->right());

  delete subroot;

}



template <class Key, class Elem, class KEComp, 
[1] [2] [3] [4] 下一页