السلام عليكم ورحمه الله وبركاته
أريد شرح AVL TREE باللغة العربية وبشكل مبسط وإن أمكن شرح برنامج له بلغة C++
أرجو توضيح الأخطا لي وباللغة العربيه ...
#include <iostream>
#include <string>
using namespace std;
//==================== MACROS ====================
#define LH +1 // Left High
#define EH 0 // Even High
#define RH -1 // Right High
// NODE Definitions
template <class TYPE>
struct NODE
{
TYPE data;
NODE *left;
int bal;
NODE *right;
}; // NODE
// Class Declaration
template <class TYPE, class KTYPE>
class AvlTree
{
private:
int count;
NODE<TYPE> *_insert(NODE<TYPE> *root,NODE<TYPE> *newPtr,bool& taller);
NODE<TYPE> *leftBalance (NODE<TYPE> *root,bool& taller);
NODE<TYPE> *rotateLeft (NODE<TYPE> *root);
NODE<TYPE> *rightBalance (NODE<TYPE> *root,bool& taller);
NODE<TYPE> *rotateRight (NODE<TYPE> *root);
NODE<TYPE> *_delete (NODE<TYPE> *root,KTYPE dltKey, bool& shorter, bool& seccess);
NODE<TYPE> *dltLeftBalance (NODE<TYPE> *root ,bool& smaller);
NODE<TYPE> *dltRightBalance (NODE<TYPE> *root ,bool& shorter);
NODE<TYPE> *_retrieve (KTYPE key,NODE<TYPE> *root);
void _traversal (void (*process) (TYPE dataproc) ,NODE<TYPE> *root);
void _destroyAVL (NODE<TYPE> *root);
public:
NODE<TYPE> *tree;
AvlTree (void);
~AvlTree (void);
bool AVL_Insert (TYPE dataIn);
bool AVL_Delete (KTYPE dltKey);
bool AVL_Retrieve (KTYPE key, TYPE& dataOut);
void AVL_Traverse (void (*process)(TYPE dataProc));
bool AVL_Empty (void);
bool AVL_Full (void);
int AVL_Count (void);
}; // class AvlTree
/*=====================Constructor====================
Initializes private data.
Pre class is being defined
Post private data initialized
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE>:: AvlTree (void)
{
//Statements
tree= NULL;
count = 0;
} // Constructor
/*==================== AVL_Insert ====================
This function inserts new data into the tree.
Pre dataln contains data to be inserted
Post data have been inserted or memory overflow Return success (true) or overflow (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Insert (TYPE dataIn)
{
//Local Definitions
NODE<TYPE> *newPtr;
bool taller;
//Statements
if (!(newPtr = new NODE<TYPE>))
return false;
newPtr->bal= EH;
newPtr->right = NULL;
newPtr->left = NULL;
newPtr->data = dataIn;
tree=_insert(tree,newPtr,taller);
count++;
return true;
} // Avl_Insert
/*======================= _insert =======================
This function uses recursion to insert the new data into a leaf node in the AVL tree.
Pre application has called AVL_Insert, which passes
root and data pointers
Post data have been inserted
Return pointer to [potentially] new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE> ::_insert(NODE<TYPE> *root,NODE<TYPE> *newPtr,bool& taller)
{
// statements
if (! root)
{
root = newPtr;
taller = true;
return root;
} // if NULL tree
if (newPtr->data.key < root->data.key)
{
root->left = _insert(root->left,newPtr,taller);
if (taller)
// Left subtree is taller
switch (root->bal)
{
case LH: // Was left high--rotate
root = leftBalance (root, taller);
break;
case EH: // Was balanced--now LH
root->bal = LH;
break;
case RH: // Was right high--now EH root->bal = EH;
taller = false;
break;
} // switch
} // new < node
else
// new data >= root data
{
root->right = _insert (root->right,newPtr,taller);
if (taller)
// Right subtree is taller
switch (root->bal)
{
case LH: // Was left high--now EH
root->bal = EH;
taller = false;
break;
case EH: // Was balanced--now RH
root->bal = RH;
break;
case RH: // Was right high--rotate
root = rightBalance (root, taller);
break;
} // switch
} // else new data >= root data
return root;
} // _insert
/*===================== rightBalance =====================
The tree is out of balance to the right This function rotates the tree to the left.
Pre the tree is right high
Post balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>:: rightBalance (NODE<TYPE> *root,bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
rightTree = root->right;
switch (rightTree->bal)
{
case RH:
root->bal= EH;
rightTree->bal = EH;
root = rotateLeft (root);
taller = false;
break;
case EH:
cout <<"\n\a\aError in leftBalance\n";
exit (100);
case LH:
leftTree = rightTree->left;
switch (leftTree->bal)
{
case RH:
root->bal= LH;
rightTree->bal = EH;
break;
case EH:
root->bal= EH;
rightTree->bal = EH;
break;
case LH:
root->bal= EH;
rightTree->bal = RH;
break;
}
leftTree->bal = EH;
root->right = rotateRight (rightTree);
root = rotateLeft (root);
taller = false;
}
return root;
}
/*===================== leftBalance =====================
The tree is out of balance to the left. This function rotates the tree to the right.
Pre the tree is left high
Post balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> *AvlTree<TYPE, KTYPE>:: leftBalance (NODE<TYPE> *root,bool& taller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
// Statements
leftTree = root->left;
switch (leftTree->bal)
{
case LH: // Left High--Rotate Right
root->bal= EH;
leftTree->bal = EH;
// Rotate Right
root = rotateRight (root);
taller = false;
break;
case EH: // This is an error
cout <<"\n\a\aError in leftBalance\n";
exit (100);
case RH: // Right High - Requires double rotation:
// first left, then right
rightTree = leftTree->right;
switch (rightTree->bal)
{
case LH:
root->bal= RH;
leftTree->bal = EH;
break;
case EH:
root->bal= EH;
leftTree->bal = EH;
break;
case RH:
root->bal= EH;
leftTree->bal = LH;
break;
} // switch rightTree
rightTree->bal = EH;
// Rotate Left
root->left = rotateLeft (leftTree);
// Rotate Right
root = rotateRight (root);
taller = false;
} // switch leftTree
return root;
} // leftBalance
/*===================== rotateLeft =====================
This function exchanges pointers so as to rotate the tree to the left.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: rotateLeft (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->right;
root->right = tempPtr->left;
tempPtr->left = root;
return tempPtr;
} // rotateLeft
/*===================== rotateRight =====================
This function exchanges pointers to rotate the tree to the right.
Pre root points to tree to be rotated
Post NODE rotated and new root returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: rotateRight (NODE<TYPE> *root)
{
// Local Definitions
NODE<TYPE> *tempPtr;
// Statements
tempPtr = root->left;
root->left= tempPtr->right;
tempPtr->right = root;
return tempPtr;
} // rotateRight
/* ====================== AVL _Delete =============--------¬
This function deletes a node from the tree and rebalances it if necessary.
Pre dltKey contains key to be deleted
Post the node is deleted and its space recycled
-or- an error code is returned
Return success (true) or not found (false)
*/
template <class TYPE, class KTYPE>
bool AvlTree <TYPE, KTYPE> :: AVL_Delete (KTYPE dltKey)
{
// Local Definitions
bool shorter;
bool success;
NODE<TYPE> *newRoot;
// statements
newRoot = _delete (tree, dltKey, shorter, success);
if (success)
{
tree = newRoot;
count--;
} // if
return success;
} //AVL_Delete
/* ======================== _delete =======================
This function deletes a node from the tree and rebalances it if necessary.
Pre dltKey contains key of node to be deleted
shorter is Boolean indicating tree is shorter
Post the node is deleted and its space recycled
-or- if key not found, tree is unchanged
Return true if deleted, false if not found pointer to root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: _delete (NODE<TYPE> *root,KTYPE dltKey,bool& shorter,bool& success)
{
// Local Definitions
NODE<TYPE> *dltptr;
NODE<TYPE> *exchPtr;
NODE<TYPE> *newRoot;
// Statements
if (! root)
{
shorter = false;
success = false;
return NULL;
} // if -- base case
if (dltKey < root->data.key)
{
root->left = _delete (root->left, dltKey,shorter, success);
if (shorter)
root = dltRightBalance (root, shorter);
} // if less
else if (dltKey> root->data.key)
{
root->right = _delete (root->right, dltKey,shorter, success);
if (shorter)
root = dltLeftBalance (root, shorter);
} // if greater
else
//Found equal node
{
dltptr = root;
if (!root->right)
// Only left subtree
{
newRoot = root->left;
success = true;
shorter = true;
delete (dltptr);
return newRoot; //base case
} // if true
else if (!root->left)
// Only right subtree
{
newRoot = root->right;
success = true; shorter = true; delete (dltptr);
return newRoot; // base case
} // if
else
// Delete NODE has two subtrees
{
exchPtr = root->left;
while (exchPtr->right)
exchPtr = exchPtr->right;
root->data = exchPtr->data;
root->left = _delete (root->left,exchPtr->data.key, shorter,success);
if (shorter)
root = dltRightBalance (root, shorter);
} // else
} // equal node
return root;
} // _delete
/* =================== dltRightBalance ==================
The tree is shorter after a delete on the left.
Adjust the balance factors and rotate the tree to the left if necessary.
Pre the tree is shorter
Post balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: dltRightBalance (NODE<TYPE> * root ,bool& shorter)
{ // Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
//Statements
switch (root->bal)
{
case LH: // Deleted Left--Now balanced
root->bal = EH;
break;
case EH: // Now Right high
root->bal = RH;
shorter = false;
break;
case RH: // Right High - Rotate Left
rightTree = root->right;
if (rightTree->bal == LH)
// Double rotation required
{
leftTree = rightTree->left;
switch (leftTree->bal)
{
case LH:
rightTree->bal = RH;
root->bal= EH;
break;
case EH:
root->bal= EH;
rightTree->bal = EH;
break;
case RH:
root->bal= LH;
rightTree->bal = EH;
break;
} // switch
leftTree->bal = EH;
// Rotate Right then Left
root->right = rotateRight (rightTree);
root= rotateLeft(root);
} // if rightTree->bal == LH
else
{
// Single Rotation Only
switch (rightTree->bal)
{
case LH:
case RH:
root->bal= EH;
rightTree->bal = EH;
break;
case EH:
root->bal= RH;
rightTree->bal = LH;
shorter = false;
break;
} // switch rightTree->bal
root = rotateLeft (root);
} // else
} // switch root bal
return root;
}// dltRiqhtBalance
/* =================== dltleftBalance ==================
The tree is shorter after a delete on the right.
Adjust the balance factors and rotate the tree to the right if necessary.
Pre the tree is shorter
Post balance factors adjusted and balance restored
Returns potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>:: dltLeftBalance (NODE<TYPE> * root ,bool& smaller)
{
// Local Definitions
NODE<TYPE> *rightTree;
NODE<TYPE> *leftTree;
//Statements
switch (root->bal)
{
case RH:
root->bal = EH;
break;
case EH:
root->bal = LH;
smaller = false;
break;
case LH:
leftTree = root->left;
if (leftTree->bal == RH)
{
rightTree = leftTree->right;
switch (rightTree->bal)
{
case RH:
leftTree->bal = LH;
root->bal= EH;
break;
case EH:
root->bal= EH;
leftTree->bal = EH;
break;
case LH:
root->bal= RH;
leftTree->bal = EH;
break;
} // switch
rightTree->bal = EH;
root->left = rotateLeft (leftTree);
root= rotateRight(root);
}
else
{
switch (leftTree->bal)
{
case RH:
case LH:
root->bal= EH;
leftTree->bal = EH;
break;
case EH:
root->bal= LH;
leftTree->bal = RH;
smaller = false;
break;
}
root = rotateRight (root);
} // else
}
return root;
}// dltleftBalance
/*==================== AVL_Retrieve ====================
Retrieve node searches the tree for the node containing the requested key and returns pointer to its data.
Pre dataOut is variable to receive data
Post tree searched and data returned
Return true if found, false if not found
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE,KTYPE>:: AVL_Retrieve (KTYPE key, TYPE& dataOut)
{
// Local Definitions
NODE<TYPE> *node;
// Statements
if (! tree)
return false;
node = _retrieve (key,tree);
if (node)
{
dataOut = node->data;
return true;
} // if found
else
return false;
} // AVL_Retrieve
/*===================== _retrieve =====================
Retrieve searches tree for node c_ntaining requested key and returns its data to the calling function.
Pre AVL_Retrieve called: passes key to be locat.
Post tree searched and data pointer returned
Return address of matching node returned
if not foundt NULL returned
*/
template <class TYPE, class KTYPE>
NODE<TYPE>* AvlTree<TYPE, KTYPE>::_retrieve (KTYPE key,NODE<TYPE> *root)
{
// statements
if (root)
{
if (key < root->data.key)
return _retrieve (key, root->left);
else if (key > root->data.key)
return _retrieve (key, root->right);
else
// Found equal key
return (root);
} // if root
else
//Data not in tree
return root;
}// _retrieve
/*==================== AVL Traverse ====================
Process tree using inorder traversal.
Pre process used to "visit" nodes during traversal
Post all nodes processed in LNR (inorder) sequence
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>:: AVL_Traverse (void (*process) (TYPE dataProc))
{
// Statements
_traversal (process, tree);
return;
}// end AVL_Traverse
/* ===================== _traversal =====================
Traverse tree using inorder traversal. To process a node, we use the function passed when traversal is called.
Pre tree has been created (may be null)
Post all nodes processed
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>:: _traversal (void(*process) (TYPE dataproc),NODE<TYPE> *root)
{ // statements
if (root)
{
_traversal (process, root->left);
process (root->data);
_traversal (process, root->right);
} // if
return;
} // _traversal
/*=================== AVL_Empty ==================
Returns true if tree is empty, false if any data.
Pre tree has been created; may be null
Returns true if tree empty, false if any data
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Empty (void)
{
//Statements
return (count == 0);
}//AVL_Empty
/*=================== AVL_Full ===================
If there is no room for another node, returns true.
Pre tree has been created
Returns true if no room, false if room
*/
template <class TYPE, class KTYPE>
bool AvlTree<TYPE, KTYPE> :: AVL_Full (void)
{
// Local Definitions
NODE<TYPE> *newPtr;
// Statements
newPtr = new NODE<TYPE>;
if (newPtr)
{
delete newPtr;
return false;
} // if
else
return true;
} // AVL_Full
/*================ AVL_count ===================
Returns number of nodes in tree.
Pre tree has been created
Returns tree count
*/
template <class TYPE, class KTYPE>
int AvlTree<TYPE, KTYPE>:: AVL_Count (void)
{
// statements
return (count);
}// AVL_count
/*=================== Destructor ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in inorder sequence.
Pre tree is a pointer to a valid tree
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
AvlTree<TYPE, KTYPE> :: ~AvlTree (void)
{
// statements
if (tree)
_destroyAVL (tree);
}// Destructor
/*=================== _destroyAvL ===================
Deletes all data in tree and recycles memory.
The nodes are deleted by calling a recursive
function to traverse the tree in postorder sequence.
Pre tree is being destroyed
Post all data have been deleted
*/
template <class TYPE, class KTYPE>
void AvlTree<TYPE, KTYPE>:: _destroyAVL (NODE<TYPE> *root)
{
// statements
if (root)
{
_destroyAVL (root->left);
_destroyAVL (root->right);
delete root;
} // if
return;
} //_ destroyAVL
//========================END========================
struct employee
{
int key;//id
string name;
int salary;
};
template <class TYPE, class KTYPE>
void Print_all (AvlTree<employee > &Avl)
{
employee emp;
int count= Avl.AVL_Count();
for (int i=0;i<count;i++)
{
Avl.AVL_Delete(emp);
cout<<emp.name<<emp.key<<emp.salary;
}
}
template <class TYPE, class KTYPE>
void Count()
{
employee emp;
return( emp.AVLCount());
}
template <class TYPE, class KTYPE>
void DeleteSpecificemployee(AvlTree<employee > &Avl)
{
employee emp;
cout<<"enter the id of employee you want delete from(97-122)"<<endl;
cin>>emp.key;
for (int i=97;i<=122;i++)
{
if (i==emp.key)
Avl.AVL_Delete(emp);
else
cout<<"employee not found";
}
}
int main ()
{
int choice;bool succ;
AvlTree<employee> Avl;
employee emp;
do {
cout<<" ******** MENU ********"<<endl;
cout<<"1. add new eployee to the company" << endl;
cout <<"2.number of employee in the company" << endl;
cout <<"3.Print all employee in the company by postorder(LRN)" << endl;
cout<< "4. Delete specific employee ." << endl;
cout <<"5. exit" << endl;
cout<<"enter choice: ";
cin >> choice;
switch(choice)
{
case 1:
cout << " Enter employee name " << endl;
cin >> emp.name;
cout << endl;
cout << " Enter employee id " << endl;
cin >> emp.key;
cout << endl;
cout << " Enter employee salary " << endl;
cin >> emp.salary;
cout << endl;
succ = Avl.AVL_Insert (emp);
if (succ)
cout << " new employee had been added " << endl;//add
else
cout << " sorry could not add this new employee " << endl;//not
break;
case 2:
cout<<"the number of employee in the company = "<<Avl.Count()<<endl;
break;
case 3:
cout<<"The information about all employee in the company"<<endl;
Print_all (emp);
cout<<"employee name : "<<emp.name<<endl<<"id: "<<emp.key<<endl<<"employee name : "<<emp.salary<<endl;
}
break;
case 4:
DeleteSpecificemployee(emp);
cout<<"Delete specific employee successful"<<endl;
break;
case 5:
break;
default:
cout << "invalid choice try again" << endl;
break;
}
} while ( choice != 5);
return 0;
}