?? avltree.h
字號:
/* AVL 樹（為了效率不從二叉搜索樹繼承）
*
*/
#ifndef AVL_TREE_CLASS
#define AVL_TREE_CLASS
#include <stdlib.h>
#include "avltreenode.h"
// 表明結點平衡因子的常量
const int leftheavy = -1;
const int balanced = 0;
const int rightheavy = 1;
template <class T>
class AVLTree
{
private:
// 指向樹根及當前結點的指針
AVLTreeNode<T> *root;
AVLTreeNode<T> *current;
// 樹中數據項個數
int size;
// 用于復制構造函數及賦值運算符
AVLTreeNode<T> *CopyTree(AVLTreeNode<T> *t);
// 用于析構函數，賦值運算符及 ClearList 方法
void DeleteTree(AVLTreeNode<T> *t);
// 在函數 Find 和 Delete 中用來定位結點及其雙親在樹中的位置
AVLTreeNode<T> *FindNode(const T& item, AVLTreeNode<T>* & parent) const;
// 供 Insert 和 Delete 方法在結點加入子樹或從子樹中刪除時重建 AVL 樹
void SingleRotateLeft (AVLTreeNode<T>* &p);
void SingleRotateRight (AVLTreeNode<T>* &p);
void DoubleRotateLeft (AVLTreeNode<T>* &p);
void DoubleRotateRight (AVLTreeNode<T>* &p);
void UpdateLeftTree (AVLTreeNode<T>* &tree, bool &reviseBalanceFactor);
void UpdateRightTree (AVLTreeNode<T>* &tree, bool &reviseBalanceFactor);
// AVL 樹的 Insert 和 Delete 方法
void AVLInsert(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, bool &reviseBalanceFactor);
void AVLDelete(AVLTreeNode<T>* &tree,
AVLTreeNode<T>* newNode, bool &reviseBalanceFactor);
public:
// 構造函數，析構函數
AVLTree(void);
AVLTree(const AVLTree<T>& tree);
~AVLTree(void);
// 賦值運算符
AVLTree<T>& operator= (const AVLTree<T>& tree);
// 標準的表處理函數
bool Find(T& item);
void Insert(const T& item);
void Delete(const T& item);
void ClearList(void);
bool ListEmpty(void) const;
int ListSize(void) const;
// 樹的特殊方法
void Update(const T& item);
AVLTreeNode<T> *GetRoot(void) const;
};
template <class T>
AVLTreeNode<T> *AVLTree<T>::CopyTree(AVLTreeNode<T> *t)
{
AVLTreeNode<T> *newlptr, *newrptr, *newNode;
if (t == NULL)
return NULL;
if (t->left != NULL)
newlptr = CopyTree(t->left);
else
newlptr = NULL;
if (t->right != 0)
newrptr = CopyTree(t->right);
else
newrptr = NULL;
newNode = new AVLTreeNode(t->data, newlptr, newrptr);
return newNode;
}
// 刪除當前對象存儲的樹
template <class T>
void AVLTree<T>::DeleteTree(AVLTreeNode<T> *t)
{
if (t != NULL)
{
DeleteTree(t->left);
DeleteTree(t->right);
delete t;
}
}
// 刪除樹中的所有結點
template <class T>
void AVLTree<T>::ClearList(void)
{
DeleteTree(root);
root = current = NULL;
size = 0;
}
template <class T>
AVLTree<T>& AVLTree<T>::operator= (const AVLTree<T>& rhs)
{
// 不能將樹復制到自身
if (this == &rhs)
return *this;
ClearList();
root = CopyTree(ths.root);
current = root;
size = ths.size;
return *this;
}
// 在樹中搜索 item，若找到，則將結點數據賦給 item
template <class T>
bool AVLTree<T>::Find(T& item)
{
// 使用 FindNode，它需要 parent 參數
AVLTreeNode<T> *parent;
// 在樹中搜索 item，將匹配的結點賦給 current
current = FindNode(item, parent);
// 若找到，則將數據賦給 item 并返回 True
if (current != NULL)
{
item = current->data;
return true;
}
else
// 在樹中沒找到 item，返回 False
return false;
}
// 指示樹是否為空
template <class T>
bool AVLTree<T>::ListEmpty(void) const
{
return (size == 0);
}
// 返回樹中的數據項個數
template <class T>
int AVLTree<T>::ListSize(void) const
{
return size;
}
template <class T>
AVLTree<T>::AVLTree(void):root(NULL), current(NULL), size(0)
{}
template <class T>
AVLTree<T>::AVLTree(const AVLTree<T>& tree)
{
root = CopyTree(tree.root);
current = root;
size = tree.size;
}
template <class T>
AVLTree<T>::~AVLTree(void)
{
ClearList();
}
// 在樹中搜索數據項，若找到，則返回結點地址及指向其雙親的指針；否則，返回 NULL
template <class T>
AVLTreeNode<T> *AVLTree<T>::FindNode(const T& item, AVLTreeNode<T>* & parent) const
{
// 用指針 t 從根開始遍歷樹
AVLTreeNode<T> *t = root;
// 根的雙親為 NULL
parent = NULL;
// 若子樹為空，則循環結束
while(t != NULL)
{
// 若找到鍵值，則退出
if (item == t->data)
break;
else
{
// 修改雙親指針，并移到左子樹或右子樹
parent = t;
if (item < t->data)
t = t->left;
else
t = t->right;
}
}
// 返回指向結點的指針；若沒找到，則返回 NULL
return t;
}
template <class T>
void AVLTree<T>::SingleRotateLeft (AVLTreeNode<T>* &p)
{
AVLTreeNode<T> *rc = p->right;
p->balanceFactor = balanced;
rc->balanceFactor = balanced;
p->right = rc->left;
rc->left = p;
p = rc;
}
// 繞結點 p 順時針旋轉；使 lc 成為新軸
template <class T>
void AVLTree<T>::SingleRotateRight (AVLTreeNode<T>* & p)
{
// p 的左子樹“超重”，將 p 的左子樹給 lc
AVLTreeNode<T> *lc = p->left;
// 修改雙親結點及左孩子的平衡因子
p->balanceFactor = balanced;
lc->balanceFactor = balanced;
// lc 的右子樹 st 應繼續為 lc 右子樹的一部分，將它改為 p 的左子樹
p->left = lc->right;
// 旋轉 p 使其為 lc 的右子樹，lc 成為新軸
lc->right = p;
p = lc;
}
template <class T>
void AVLTree<T>::DoubleRotateLeft (AVLTreeNode<T>* &p)
{
AVLTreeNode<T> *rc, *np;
rc = p->right;
np = rc->left;
if (np->balanceFactor == leftheavy)
{
p->balanceFactor = balanced;
rc->balanceFactor = leftheavy;
}
else if (np->balanceFactor == balanced)
{
p->balanceFactor = balanced;
rc->balanceFactor = balanced;
}
else
{
p->balanceFactor = leftheavy;
rc->balanceFactor = balanced;
}
np->balanceFactor = balanced;
rc->left = np->right;
np->right = rc;
p->right = np->left;
np->left = p;
p = np;
}
// 繞結點 p 雙右旋
template <class T>
void AVLTree<T>::DoubleRotateRight (AVLTreeNode<T>* &p)
{
// 被旋轉的兩個子樹
AVLTreeNode<T> *lc, *np;
// 在樹中，結點(lc) < 結點(np) < 結點(p)
lc = p->Left(); // lc 為雙親的左孩子
np = lc->Right(); // np 為 lc 的右孩子
// 修改 p, lc 和 np 的平衡因子
if (np->balanceFactor == rightheavy)
{
p->balanceFactor = balanced;
lc->balanceFactor = rightheavy;
}
else if (np->balanceFactor == balanced)
{
p->balanceFactor = balanced;
lc->balanceFactor = balanced;
}
else
{
p->balanceFactor = rightheavy;
lc->balanceFactor = balanced;
}
np->balanceFactor = balanced;
// 在 np 替代雙親 p 之前，注意卸掉其老子樹，連上新子樹
lc->right = np->left;
np->left = lc;
p->left = np->right;
np->right = p;
p = np;
}
template <class T>
void AVLTree<T>::UpdateLeftTree (AVLTreeNode<T>* &p, bool &reviseBalanceFactor)
{
AVLTreeNode<T> *lc = p->left; // 左子樹邊偏重
if (lc->balanceFactor == leftheavy)
{
SingleRotateRight(p); // 需單旋轉
reviseBalanceFactor = false;
}
// 右子樹偏重嗎？
else if (lc->balanceFactor == rightheavy)
{
// 做一次雙旋轉
DoubleRotateRight(p);
// 此時，根結點平衡了
reviseBalanceFactor = false;
}
}
template <class T>
void AVLTree<T>::UpdateRightTree (AVLTreeNode<T>* &p, bool &reviseBalanceFactor)
{
AVLTreeNode<T> *rc = p->right;
if (rc->balanceFactor == rightheavy)
{
SingleRotateLeft(p);
reviseBalanceFactor = false;
}
else if (rc->balanceFactor == leftheavy)
{
DoubleRotateLeft(p);
reviseBalanceFactor = false;
}
}
template <class T>
void AVLTree<T>:: AVLInsert(AVLTreeNode<T>* & tree,
AVLTreeNode<T>* newNode, bool &reviseBalanceFactor)
{
// 是否需修改結點的 balanceFactor 值的標志
bool rebalanceCurrNode;
// 掃描到空子樹；此時應插入新節點
if (tree == NULL)
{
// 更新雙親結點使其指向新節點
tree = newNode;
// 將新結點的 balanceFactor 賦值為 0
tree->balanceFactor = balanced;
// 廣播消息；balanceFactor 值被改變
reviseBalanceFactor = true;
}
// 若新結點的數據值 < 當前數據值，則遞歸遍歷左子樹
else if (newNode->data < tree->data)
{
AVLInsert(tree->left, newNode, rebalanceCurrNode);
// 檢查是否應修改 balanceFactor 值
if (rebalanceCurrNode)
{
// 從左偏重的子樹往左，將違背 AVL 條件，進行旋轉（情況3）
if (tree->balanceFactor == leftheavy)
UpdateLeftTree(tree,reviseBalanceFactor);
// 從平衡結點往左，往左子樹增加結點，滿足 AVL 條件（情況 1）
else if (tree->balanceFactor == balanced)
{
tree->balanceFactor = leftheavy;
reviseBalanceFactor = true;
}
// 從右偏重子樹往左，將產生平衡子樹，滿足 AVL 條件（情況 2）
else
{
tree->balanceFactor = balanced;
reviseBalanceFactor = false;
}
}
else
// 不需平衡此結點，也不用平衡上結點
reviseBalanceFactor = false;
}
// 否則，遞歸遍歷右子樹
else
{
AVLInsert(tree->right, newNode, rebalanceCurrNode);
// 檢查是否應修改 balanceFactor 值
if (rebalanceCurrNode)
{
// 從左偏重子樹往右，將平衡結點，滿足 AVL 條件（情況 2）
if (tree->balanceFactor == leftheavy)
{
// 掃面右子樹，結點左偏重，則將成為平衡結點
tree->balanceFactor = balanced;
reviseBalanceFactor = false;
}
// 從平衡子樹往右，將產生右偏重結點，滿足 AVL 條件（情況 1）
else if (tree->balanceFactor == balanced)
{
// 結點原為平衡；將成為右偏重
tree->balanceFactor = rightheavy;
reviseBalanceFactor = true;
}
else
// 從右偏重結點向右，將違背 AVL 條件，應進行旋轉（情況 3）
UpdateRightTree(tree, reviseBalanceFactor);
}
else
reviseBalanceFactor = false;
}
}
template <class T>
void AVLTree<T>::Insert(const T& item)
{
// 定義指向 AVL 樹結點的指針
AVLTreeNode<T> *treeRoot = root, *newNode;
// 供 AVLInsert 重新平衡結點的標志
bool reviseBalanceFactor = false;
newNode = new AVLTreeNode<T>(item,NULL,NULL);
// 調用遞歸函數實際插入元素
AVLInsert(treeRoot, newNode, reviseBalanceFactor);
// 賦新值給基類中的數據成員
root = treeRoot;
current = newNode;
size++;
}
// 若當前結點已定義且數據值與給定數據值相等，則將結點值賦給 item；否則，將 item 插入到樹中
template <class T>
void AVLTree<T>::Update(const T& item)
{
if (current != NULL && current->data == item)
current->data = item;
else
Insert(item);
}
// 返回根結點的地址
template <class T>
AVLTreeNode<T> *AVLTree<T>::GetRoot(void) const
{
return root;
}
template <class T>
void AVLTree<T>::AVLDelete(AVLTreeNode<T>* &tree, AVLTreeNode<T>* newNode, bool &reviseBalanceFactor)
{
// 太過復雜，又不常用（AVL 樹應主要用于初始化，因為其插入或刪除的成本過高）
throw "AVLTree::AVLDelete: Function not implement";
}
template <class T>
void AVLTree<T>::Delete(const T& item)
{
throw "AVLTree::Delete: Function not implement";
}
#endif // AVL_TREE_CLASS
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -