📄 avltreeadt.h
字号:
// =================== 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; //1
NODE<TYPE> *tree; //2
NODE<TYPE> *_insert (NODE<TYPE> *root,
NODE<TYPE> *nerPtr,
bool& taller); //1
NODE<TYPE> *leftBalance (NODE<TYPE> *root,
bool& taller); //2
NODE<TYPE> *rotateLeft (NODE<TYPE> *root); //3
NODE<TYPE> *rightBalance (NODE<TYPE> *root,
bool& taller); //4
NODE<TYPE> *rotateRight (NODE<TYPE> *root); //5
NODE<TYPE> *_delete (NODE<TYPE> *root,
KTYPE dltKey,
bool& shorter,
bool& success); //6
NODE<TYPE> *dltLeftBalance (NODE<TYPE> *root,
bool& smaller); //7
NODE<TYPE> *dltRightBalance (NODE<TYPE> *root,
bool& shorter); //8
NODE<TYPE> *_retrieve (KTYPE Key,
NODE<TYPE> *root); //9
void _traversal (void(*process)(TYPE dataProc),
NODE<TYPE> *root); //10
void _destroyAVL (NODE<TYPE> *root); //11
public:
AvlTree (void); //12
~AvlTree (void); //13
bool AVL_Insert (TYPE dataIn); //14
bool AVL_Delete (KTYPE dataKey); //15
bool AVL_Retrieve (KTYPE Key,
TYPE& dataOut); //16
void AVL_Traverse (void (*process)(TYPE dataProc)); //17
bool AVL_Empty (void); //18
bool AVL_Full (void); //19
int AVL_Count (void); //20
};
/* =================== _Insert ================== //1
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 has 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 = 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
/* =================== leftBalance ================== //2
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
Return 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->right;
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 ================== //3
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
/* =================== rightBalance ================== //4
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
Return potentially new root
*/
template <class TYPE, class KTYPE>
NODE<TYPE> * AvlTree<TYPE, KTYPE>
:: rightBalance (NODE<TYPE> *root,
bool& taller)
{
// Local Definitions
NODE<TYPE> *leftTree;
NODE<TYPE> *rightTree;
// Statements
rightTree = root->right;
switch (rightTree->bal)
{
case RH: // right high--Rotate Left
root->bal = EH;
rightTree->bal = EH;
// Rotate Left
root = rotateLeft (root);
taller = false;
break;
case EH: // This is an error
cout <<"\n\a\aError in rightBalance\n";
exit(100);
case LH: // Left high - Requires double rotation:
// first right, then left
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;
} // switch leftTree
leftTree->bal = EH;
// Rotate right
root->right = rotateRight (rightTree);
// Rotate Left
root = rotateLeft (root);
taller = false;
} // switch rightTree
return root;
} // rightBalance
/* =================== rotateRight ================== //5
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
/* =================== _delete ================== // 6
This function deletes a node from the tree and rebalances
it if nessary.
Pre dltKey contains key 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 is 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
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
/* =================== dltLeftBalance ================== //7
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,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -