Avl tree template implementation (increasing REMOVE method)

http://www.staroceans.com/avltree-remove.htm

AVLTREE (with remove)

A. SECOND Edition

THIS Second Edition of My AVL Tree and The Reason I Restart This Project Is That I WAS Blamed for Not Finishing

Remove Function. so, let's finish it and it is so "ad-hoc".

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 thank triabst, it is expected That We need to

Reduce As Many "Balancing Operations" as Possible.

C.THE

Idea of ​​Program

The main idea is similar to "insert" Except That Trouble Node Is Not Always At Same Side AS

THE REMOVED NODE, WHILE for Inserting, IT IS Always The Case. One More Problem Is That The Son Node

Of the "axis" Node Can Have A Balance Factor of 0! What's Worse, His Brother May Also Has 0 AS ITS

Balance Factor While THEIR PARENT HAS A /- 2 As Factor! What Should We Do About It? It Seems There

Is No Algorithm About Remove. SHOULD I Check "Data Structure" Text Book for Confirmation?

D.The Major Functions

Bool Insert (Const Elem & E)

Do you expect what 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 evenu "inserthelp" is not virtual.

2. BinNode * Inserthelp (BinNode *, 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 inserated new leaf along path. and before what Insertion, i Placed A Road

Sign "inleaf" to indicate Which side the path takes.3. Void UpdateHeight (binnode * & subroot);

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

And try to keep it 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 * subroot);

I Resist to Use recursive method Because The Field "Height" is a short-cut.

5. Binnode * SingleroTate (BinNode * Parent, Bool IsRoot, Bool Left2Right);

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

Bottom-Up.

6. BinNode * Doublerotate (BinNode * Parent, Bool Isroot, Bool Left2Right);

I Made it looks simple by adding the "dodouble" and quite satisfy with it.

E.Further Improvement

F.File Listing

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 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 childvirtual void setright (binnode *) = 0;

// Return True iff the node is a leaf

Virtual bool isleaf () = 0;

// my Personal Preference

Virtual binnode * getson (bool isleft) const = 0;

// my Personal Preference

Virtual Void Setson (BinNode * SON, BOOL ISLEFT) = 0;

}

// binary Tree Node Class

Template

Class Binnodeptr: Public BinNode {

Private:

Elem it; // the node's value

Binnodeptr * lc; // Pointer to Left Child

Binnodeptr * rc; // Pointer to Right Child

PUBLIC:

// Two Constructors - with and welst 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 * left () const {return lc;}

Void setleft (binnode * b) {lc = (binnodeptr *) b;}

Inline binnode * right () const {return rc;}

Void setRight (binnode * b) {rc = (binnodeptr *) b;}

Bool isleaf () {return (lc == null) && (rc == null);

BinNode * getson (BOOL ISLEFT) const {return isleft? Lc: rc;}

Void Setson (BinNode * SON, BOOL ISLEFT)

{

ISLEFT? SETLEFT (SON): SetRight (SON);

}

}

Template

Class AvlnodePtr: Public BinNode

{

protected:

Elem it; // the node's value

AVLNODEPTR * LC; // Pointer to Left Child

AVLNODEPTR * RC; // Pointer to Right Child

INT height;

BOOL INEFT;

PUBLIC:

// Two constructors - with and welstr () {lc = rc = null; height = 1; inleft = true;

AVLNODEPTR (ELEM E, AVLNODEPTR * L = NULL,

AVLNODEPTR * 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 * left () const {return lc;}

Void setleft (binnode * b) {lc = (avlnodeptr *) b;}

Inline binnode * right () const {return rc;}

Void setRight (binnode * b) {rc = (avlnodeptr *) b;}

Bool isleaf () {return (lc == null) && (rc == null);

Void setHeight (int newhem) {height = newheight;

Int getHeight () {Return Height;

BinNode * getson (BOOL ISLEFT) const {return isleft? Lc: rc;}

Bool getside () const {return inleft;

Void setside (bool isleft) {inleft = isleft;}

Void Setson (BinNode * SON, BOOL ISLEFT)

{

ISLEFT? SETLEFT (SON): SetRight (SON);

}

}

File name: bst.h

// this file incruDes all of the bascs of the bst implementation

#include "dictionary.h"

#include "binnode.h"

// binary search Tree Implementation for the Dictionary ADT

Template

Class Bst: Public Dictionary {

protected:

BinNode * root; // root of the bst

Int nodecount; // Number of Nodes in the BST

// Private "Helper" Functions

Void ClearHelp (BinNode *);

BinNode * InsertHelp (BinNode *, Const ELEM &);

BinNode * deletemin (binnode *, binnode *); binnode * removehelp (binnode *, const key)

BinNode * &);

Bool Findhelp (BinNode *, Const Key &, ELEM &) Const;

Void Printhelp (binnode *, 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 * 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 * 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

Void Bst ::

ClearHelp (BinNode * Subroot) {

IF (Subroot == Null) return;

ClearHelp (Subroot-> LEFT ());

ClearHelp (Subroot-> Right ());

Delete subroot;

}

Template

BinNode * BST ::

INSERTHELP (BinNode * Subroot, Const Elem & Val {if (Subroot == Null) // EMPTY Tree: Create Node

Return (New Binnodeptr (VAL, NULL, NULL);

IF (EECOMP :: LT (Val, Subroot-> Val ())) // Insert On LEFT

Subroot-> setleft (INSERTHELP (Subroot-> LEFT (), VAL);

Else Subroot-> SetRight (INSERTHELP (Subroot-> Right (), VAL);

Return Subroot; // Return Subtree with node inserted

}

Template

BinNode * BST ::

Deletemin (BinNode * Subroot, BinNode * & min) {

IF (Subroot-> Left () == null) {// Found min

min = Subroot;

RETURN SUBROOT-> Right ();

}

Else {// Continue LEFT

Subroot-> setleft (deletemin (subroot-> left (), min);

Return Subroot;

}

}

Template

BinNode * BST ::

Removehelp (BinNode * Subroot, Const Key & K,

BinNode * & t) {

IF (Subroot == Null) Return Null; // Val is Not in Tree

Else IF (kecomp :: lt (k, suck ot-> val ()) // Check Left

Subroot-> Setleft (removehelp (subrowhelp (subroot-> left (), k, t));

Else IF (kecomp :: gt (k, subroot-> val ()) // Check Right

Subroot-> SetRight (RemoveHelp (Subroot-> Right (), K, T);

Else {// Found IT: REMOVE IT

BinNode * TEMP;

T = SUBROOT;

IF (Subroot-> Left () == null) // Only a Right Child

Subroot = Subroot-> Right (); // so point to right

Else IF (Subroot-> Right () == null) // Only a left child

Subroot = Subroot-> Left (); // so point to leavelse {// Both Children Are Non-Empty

Subroot-> SetRight (deletemin (Subroot-> Right (), TEMP);

ELEM TE = Subroot-> Val ();

Subroot-> SetVal (TEMP-> VAL ());

Temp-> SetVal (TE);

T = TEMP;

}

}

Return Subroot;

}

Template

Bool Bst :: findhelp

BinNode * Subroot, Const Key & K, Elem & E) Const {

IF (Subroot == Null) Return False; // EMPTY TREE

Else IF (kecomp :: lt (k, suck ot-> val ()) // Check Left

Return FindHelp (Subroot-> Left (), K, E);

Else IF (kecomp :: gt (k, subroot-> val ()) // Check Right

Return FindHelp (Subroot-> Right (), K, E);

Else {E = Subroot-> Val (); Return True;} // Found IT

}

Template

Void Bst ::

Printhelp (BinNode * Subroot, Int Level) const {

IF (Subroot == Null) Return; // EMPTY TREE

Printhelp (Subroot-> Left (), Level 1); // Do Left Subtree

For (int i = 0; i

Cout << ";

COUT << Subroot-> Val () << "/ n"; //print node value

Printhelp (Subroot-> Right (), Level 1); // DO Right Subtree

}

FILE NAME: Dictionary.h

// The Dictionary Abstract Class. Kecomp Compares a Key

// and an element. EECOMP Compares Two Elements.

Template

Class Dictionary {

PUBLIC:

// Reinitialize Dictionary

Virtual void clear () = 0;

// INSERT AN Element. Return True if INSERT IS

// Successful, False OtherWise.Virtual Bool INSERT (Const Elem &) = 0;

// Remove Some Element Matching Key. Return True IF Such

// exists, false otherwise. if Multiple Entries Match

// Key, an Arbitrary One is removed.

Virtual Bool Remove (Const Key &, ELEM &) = 0;

// Remove and return an Arbitrary Element from Dictionary.

// Return True if some element is found, false Otherwise.

Virtual Bool Removeany (ELEM &) = 0;

// Return a copy of some elem matching key. Return True

// if Such exists, false otherwise. if Multiple Elements

// Match Key, Return an Arbitrary One.

Virtual Bool Find (Const Key &, ELEM &) Const = 0;

// Return The Number of Elements in the DICTIONARY.

Virtual int size () = 0;

}

File name: ELEM.H

// this is the element of login system

Class Kecomp

{

PUBLIC:

Static Bool LT (Int Key, Int Elem) {Return Key

Static Bool EQ (Int Key, Int Elem) {Return Key == ELEM;

Static Bool GT (Int Key, Int Elem) {Return Key> ELEM;}

}

Class EECOMP

{

PUBLIC:

Static Bool LT (Int E1, INT E2)

{RETURN E1

Static Bool EQ (Int E1, INT E2)

{RETURN E1 == E2;

Static Bool GT (Int E1, INT E2)

{RETURN E1> E2;}

}

FILE NAME: AVLTREE.H

#include "bst.h"

Template

Struct Descriptor

{

Binnode * Parent;

Bool isroot;

Bool isleft;

Bool issingle;

Bool Left2Right;

}

Template

Class AVL: Public BST

{

protected:

// binnode * StartPtr;

Void ClearHelp (BinNode *);

Virtual Binnode * Inserthelp (BinNode *, Const ELEM &);

Bool FindHelp (Binnode *, Const Key &, ELEM &) Const; Void Printhelp (BinNode *, Int) Const;

Void UpdateHeight (BinNode * & Subroot);

INT getFactor (BinNode * Subroot);

Void Adjust (BinNode * & Subroot, Bool IsRoot);

INT gettreeheight (binnode * subroot);

Void Adjustheight (BinNode * Subroot);

BinNode * SingleroTate (BinNode * Parent, Bool Isroot, Bool Left2Right);

BinNode * Doublerotate (BinNode * Parent, Bool Isroot, Bool Left2Right);

Void Checkdir (BinNode * Subroot, Bool & Issingle, Bool & Left2Right);

BinNode * DODOUBLE (BinNode * Oldroot, Bool Left2Right);

Virtual BinNode * Deletemin (BinNode *, BinNode * &);

Virtual BinNode * RemoveHelp (BinNode *, Const Key &, BinNode * &);

PUBLIC:

AVL () {root = null; nodecount = 0;} // constructor

~ Avl () {clearhelp (root); root = null;} // destructor

/ *

BOOL INSERT (Const Elem & E)

{

Root = INSERTHELP (root, e);

NodeCount ;

Return True;

}

* /

}

// Do Not Use Recursive !!!!!

Template

Int avl :: gettreeheight (binnode * subroot)

{

AVLNODEPTR * PTR, * L, * R;

Int Newheight, Lheight, Rheight; //, Factor; // Sonfactor;

IF (Subroot == Null)

{

Return 0;

}

PTR = (AVLNODEPTR *) Subroot;

L = (AVLNODEPTR *) PTR-> LEFT ();

R = (AVLNODEPTR *) PTR-> Right ();

IF (l == NULL)

{

LHEIGHT = 0;

}

Else

{

LHEIGHT = L-> getHeight ();

}

IF (r == null)

{

RHEIGHT = 0;

}

Else

{

RHEIGHT = r-> getHeight ();

}

NEWHEIGHT = 1 (LHEIGHT> RHEIGHT? LHEIGHT: RHEIGHT);

Return newheight;

}

Template

Void AVL :: adjustheight (binnode * subroot)

{

INT height;

IF (Subroot == Null)

{

Return;

}

Height = Gettreeheight (Subroot);

((AVLNODEPTR *) -> setHeight (Height);

}

Template

BinNode * AVL :: dodouble (binnode * Oldroot,

BOOL LEFT2RIGHT)

{

BinNode * small, * mid, * big, * t1, * t2, * t3, * t4;

IF (left2right)

{

BIG = OldRoot; // the root;

Small = Oldroot-> Left ();

MID = Small-> Right ();

T1 = small-> left ();

T2 = MID-> Left ();

T3 = MID-> Right ();

T4 = BIG-> Right ();

}

Else

{

Small = OldRoot;

BIG = small-> right ();

MID = BIG-> Left ();

T1 = small-> left ();

T2 = MID-> Left ();

T3 = MID-> Right ();

T4 = BIG-> Right ();

}

MID-> setleft (small);

MID-> setRight (BIG);

Small-> setleft (t1);

Small-> setRight (T2);

BIG-> SETLEFT (T3);

BIG-> SETRIGHT (T4);

Adjustheight (small);

Adjustheight (BIG);

Adjustheight (MID);

Return MID;

}

Template

BinNode * AVL :: DoubleroTate (binnode * parent,

Bool isroot, Bool Left2Right

{

Binnode * oldroot;

Bool isleft;

IF (isroot)

{

Oldroot = Parent;

Root = DODOUBLE (Oldroot, Left2Right);

Return root; // Because We need Parent Return As Real root

}

Else

{

iSleft = ((AVLNODEPTR *) Parent) -> getside (); oldroot = parent-> getson (isleft);

Parent-> Setson (DODOUBLE (Oldroot, Left2Right), Isleft;

Adjustheight (PARENT);

Return Parent;

}

}

// if isroot, we don't need itft, it is useful when is not root and

// We need to know Which Son IT Is in

Template

BinNode * AVL :: singlerotate (binnode * parent,

Bool isroot, Bool Left2Right

{

BinNode * oldroot = parent, * SON, * T1;

Bool isleft = ((AVLNODEPTR *) Parent) -> getside ();

IF (isroot)

{

SON = Parent-> Getson (Left2Right);

T1 = SON-> Getson (! LEFT2RIGHT);

SON-> Setson (PARENT,! LEFT2RIGHT);

Parent-> Setson (T1, Left2Right);

Adjustheight (PARENT); // Sequence Is Very Important!

Adjustheight (SON); // Sequence Is Very Important!

Root = SON;

Return Son; // Because Now, we need return son as parent;

/ *

SON = Parent-> Getson (isleft);

T1 = SON-> Getson (! LEFT2RIGHT);

SON-> Setson (PARENT,! LEFT2RIGHT);

Parent-> Setson (T1, Left2Right);

// Because Parent Is At Lower Level Now, We NEED Adjust Parent First !!!

Adjustheight (PARENT); // Sequence Is Very Important!

Adjustheight (SON); // Sequence Is Very Important!

Root = SON;

Return Son; // Because Now, we need return son as parent;

* /

}

Else

{

// for non-root rotation, Parent Doesn't change !!!!!

// IT is now Very Concise !!

Oldroot = parent-> getson (isleft);

SON = Oldroot-> getson (left2right); // this is the trick!

T1 = SON-> Getson (! LEFT2RIGHT);

Parent-> setson (SON, ISLEFT);

Oldroot-> Setson (T1, LEFT2RIGHT);

SON-> Setson (Oldroot,! Left2right);

// sequence is very import !!! Adjustheight (Oldroot);

Adjustheight (SON);

Adjustheight (PARENT); // Adjust sequence: from low to high !!!

Return Parent;

}

}

// check the direction of rotation by return value in Reference

Template

Void AVL :: checkdir (binnode * Subroot,

Bool & Issingle, Bool & Left2Right

{

BinNode * SON;

INT ParentFactor, Sonfactor;

Bool isleft;

ISLEFT = ((AVLNODEPTR *) Subroot) -> getside ();

SON = Subroot-> Getson (isleft);

ParentFactor = getFactor (Subroot);

// TO DO

SONFACTOR = GetFactor (SON);

IF (Sonfactor == 0)

{

SON = Subroot-> Getson (! isleft);

SONFACTOR = GetFactor (SON);

IF (Sonfactor == 0)

{

Issingle = true;

LEFT2RIGHT = PARENTFAACTOR> 0;

Return;

}

}

Issingle = perentfactor * Sonfactor> 0; // Same Sign

LEFT2RIGHT = PARENTFAACTOR> 0;

}

// if isroot, isleft will be ignored.

Template

Void AVL :: adjut (binnode * & subroot, bool isroot)

{

BinNode * TEMP;

Bool Issingle, Left2Right, Isleft

IF (isroot)

{

Temp = Subroot;

}

Else

{

// Use its Son to Check

ISLEFT = ((AVLNODEPTR *) Subroot) -> getside ();

Temp = Subroot-> Getson (isleft);

/ *

IF (getFactor (TEMP) == 0)

{

Temp = Subroot-> Getson (! isleft);

}

* /

}

Checkdir (Temp, Issingle, Left2Right);

IF (issingle)

{

// IT helps reading and for singlelerotate isleft is ignored when is isroot

Subroot = SingleroTate (Since, IsoT, Left2Right);

}

Else

{

Subroot = DoubleRotate (Subroot, IsRoot, Left2Right);

}

}

Template

Int avl :: getFactor (binnode * subroot)

{

Int Lheight, Rheight;

AVLNODEPTR * PTR, * L, * R;

IF (Subroot == Null)

{

Return 0;

}

PTR = (AVLNODEPTR *) Subroot;

L = (AVLNODEPTR *) (Ptr-> Left ());

R = (AVLNODEPTR *) (Ptr-> Right ());

IF (l == NULL)

{

LHEIGHT = 0;

}

Else

{

LHEIGHT = L-> getHeight ();

}

IF (r == null)

{

RHEIGHT = 0;

}

Else

{

RHEIGHT = r-> getHeight ();

}

RETURN LHEIGHT-RHEIGHT;

}

Template

Void AVL :: updateHeight (binnode * & subroot)

{

INT FACTOR, SONFACTOR;

Bool isleft;

BinNode * SON;

IF (Subroot == Null)

{

Return;

}

Adjustheight (Subroot);

Factor = getFactor (Subroot);

ISLEFT = ((AVLNODEPTR *) Subroot) -> getside ();

SON = Subroot-> Getson (isleft);

SONFACTOR = GetFactor (SON);

// First Situation: The First 2 / -2 WE Meet from bottom-Up

IF ((Factor == 2 || Factor == - 2) && subroot == root)

{

// a Special Case !!! As we search from bottom up

// We May Wait To Adjust Until We Reach ITS Father

// The Father Happens to be root. But it is not a

// root adjustment !!!

IF (SONFACTOR == 1 || SONFAACTOR == - 1 || Sonfactor == 0)

{

Adjust (Subroot, True);

}

Else

{

Adjust (Subroot, False);

}

}

Else

{

IF (SONFACTOR == 2 || SONFACTOR == - 2)

{

Adjust (Subroot, False);

}

}

}

Template

BinNode * AVL :: inserthelp (binnode * subroot, const elem & val

{

IF (Subroot == Null) // EMPTY Tree: Create Node

{

Return (New Avlnodeptr (Val, NULL, NULL, 1);

}

IF (EECOMP :: LT (Val, Subroot-> Val ())) // Insert On LEFT

{

((AVLNODEPTR *) Subroot) -> Setside (TRUE);

Subroot-> setleft (INSERTHELP (Subroot-> LEFT (), VAL);

UpdateHeight (Subroot);

}

Else

{

((AVLNODEPTR *) Subroot) -> Setside (false);

Subroot-> SetRight (Inserthelp (Subroot-> Right (), VAL);

UpdateHeight (Subroot);

}

Return Subroot; // Return Subtree with node inserted

}

Template

BinNode * AVL ::

RemoveHelp (BinNode * Subroot, Const Key & K, BinNode * & T)

{

IF (Subroot == Null)

{

Return null; // Val is not in Tree

}

Else

{

IF (kecomp :: lt (k, subroot-> val ()) // check left

{

((AVLNODEPTR *) Subroot) -> Setside (TRUE);

Subroot-> Setleft (removehelp (subrowhelp (subroot-> left (), k, t));

// UpdateHeight (Subroot);

}

Else

{

IF (kecomp :: gt (k, subroot-> val ())) // Check Right

{

((AVLNODEPTR *) Subroot) -> Setside (false);

Subroot-> SetRight (RemoveHelp (Subroot-> Right (), K, T);

// UpdateHeight (Subroot);

}

Else

{// Found IT: REMOVE IT

BinNode * TEMP;

T = SUBROOT;

IF (Subroot-> Left () == null) // Only a Right Child

{

Subroot = Subroot-> Right (); // so point to right

}

Else

{

IF (Subroot-> Right () == null) // Only a Left Child

{

Subroot = Subroot-> Left (); // so point to let}

Else

{

// Both Children Are Non-Empty

Subroot-> SetRight (deletemin (Subroot-> Right (), TEMP);

ELEM TE = Subroot-> Val ();

Subroot-> SetVal (TEMP-> VAL ());

Temp-> SetVal (TE);

T = TEMP;

((AVLNODEPTR *) Subroot) -> Setside (false);

// UpdateHeight (Subroot);

}

}

}

}

}

UpdateHeight (Subroot);

Return Subroot;

}

Template

BinNode * AVL ::

Deletemin (BinNode * Subroot, BinNode * & min)

{

IF (Subroot-> Left () == NULL)

{// Found min

min = Subroot;

RETURN SUBROOT-> Right ();

}

Else

{//Undinue left

((AVLNODEPTR *) Subroot) -> Setside (TRUE);

Subroot-> setleft (deletemin (subroot-> left (), min);

UpdateHeight (Subroot);

Return Subroot;

}

}

Template

Void AVL :: clearhelp (binnode * subroot)

{

IF (Subroot == Null)

{

Return;

}

ClearHelp (Subroot-> LEFT ());

ClearHelp (Subroot-> Right ());

Delete subroot;

}

FILE NAME: AVLTREE.CPP (Main)

#include

#include

#include "avltree.h"

#include "elem.h"

Using namespace std;

int main ()

{

Int Num;

AVL a;

// SRAND (Time (0));

For (int i = 0; i <20; i )

{

Cout << "====================";

Num = rand ()% 100 12;

COUT << "INSERT NUMBER" << Num << Endl;

A.Nsert (NUM);

A.print ();

}

For (i = 0; i <20; i )

{

Int temp;

NUM;

A.Remove (NUM, TEMP);

COUT << "/ nnow remove number" << Num << endl;

A.print ();

}

Return 0;

}

Here Is The Result: Please Note That there is area

Single Rotating While Inserting Number 90, 93, 107,

Double Rotating While Inserting Number 36, 74,

=================== Insert Number 53

53

=================== Insert Number 79

53

79

=================== Insert Number 46

46

53

79

=================== Insert Number 12

12

46

53

79

=================== Insert Number 81

12

46

53

79

81

=================== Insert Number 36

12

36

46

53

79

81

=================== Insert Number 90

12

36

46

53

79

81

90

=================== Insert Number 70

12

36

46

53

70

79

81

90

=================== Insert Number 74

12

36

46

53

70

74

79

81

90

=================== Insert Number 76

12

36

46

53

70

74

76

79

81

90

Input the Number to Remove: 79

Now remove number79

12

36

4653

70

74

76

81

90

Input the Number to Remove: 12

Now remove Number12

36

46

53

70

74

76

81

90

Input the Number to Remove: 46

Now remove number46

36

53

70

74

76

81

90

Input the Number to Remove: 81

Now remove number81

36

53

70

74

76

90

Input the Number to Remove: 76

Now remove number76

36

53

70

74

90

Input the Number to Remove: 90

Now remove number90

36

53

70

74

Input the Number to Remove: 36

Now remove number36

53

70

74

Input the Number to Remove: 70

Now remove number70

53

74

Input the Number to Remove: 74

Now remove Number74

53

Input the Number to Remove: 53

Now remove number53

The bst is empty.

Press any key to continche