溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
AVL樹是平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。查找、插入和刪除在平均和最壞情況下都是O（log n）。增加和刪除可能需要通過一次或多次樹旋轉來重新平衡這個樹。它能保持二叉樹的高度平衡，盡量降低二叉樹的高度，減少樹的平均搜索長度。
AVL樹的性質
左子樹和右子樹的高度之差的絕對值不超過1
樹中的每個左子樹和右子樹都是AVL樹
節點的平衡因子是它的左子樹的高度減去它的右子樹的高度。帶有平衡因子 1、0 或 -1 的節點被認為是平衡的。帶有平衡因子 -2 或 2 的節點被認為是不平衡的，并需要重新平衡這個樹。平衡因子可以直接存儲在每個節點中，或從可能存儲在節點中的子樹高度計算出來。
#include<iostream>
using namespace std;
//平衡搜索二叉樹
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode(K& key, V& val)
:_key(key)
, _val(val)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _bf(0)
{}
K _key;
V _val;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;// Balance Factor
};
template<class K,class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree()
:_root(NULL)
{}
bool Insert(K& key,V& val)
{
if (_root == NULL)
{
_root = new Node(key, val);
return true;
}
else
{
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
return false;
}
cur = new Node(key, val);
if (parent->_key > key)
{
parent->_left = cur;
cur->_parent = parent;
}
else
{
parent->_right = cur;
cur->_parent = parent;
}
//更新平衡因子，不平衡進行旋轉
while (parent != NULL)
{
if (cur == parent->_left)
++parent->_bf;
else
--parent->_bf;
//跳出條件
if (parent->_bf == 0)
break;
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
else//-2 2旋轉
{
if (parent->_bf == 2)
{
if (1== cur->_bf)//右旋
{
RotateR(parent);
}
else//左右旋
{
RotateLR(parent);
}
}
else
{
if (1== cur->_bf)//左右旋
{
RotateRL(parent);
}
else//左旋
{
RotateL(parent);
}
}
break;
}
}
return true;
}
}
Node* Find(K& key)
{
if (_root == NULL)
return false;
else
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
cur = cur->_left;
else if (cur->_key < key)
cur = cur->_right;
else
return cur;
}
return NULL;
}
}
bool Remove(K& key)
{
if (_root == NULL)
return false;
Node* cur = _root;
Node* parent = NULL;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key>key)
{
parent = cur;
cur = cur->_left;
}
else
{
Node* del = NULL;
if (cur->_left == NULL)
{
del = cur;
if (cur == _root)
{
_root = cur->_right;
_root->_parent = NULL;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
cur->_parent = parent;
}
else
{
parent->_right = cur->_right;
cur->_parent = parent;
}
}
}
else if (cur->_right==NULL)
{
del = cur;
if (cur == _root)
{
_root = cur->_left;
_root->_parent = NULL;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
cur->_parent = parent;
}
else
{
parent->_right = cur->_left;
cur->_parent = parent;
}
}
}
else//左右都不為空
{
Node* rightMin = root->_right;
Node* parent = root;
while (rightMin->_left)
{
parent = rightMin;
rightMin = rightMin->_left;
}
root->_key = rightMin->_key;
root->_val = rightMin->_val;
del = rightMin;
if (parent->_left == rightMin)
parent->_left = NULL;
else
parent->_right = NULL;
}
delete del;
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
}
bool IsBalance()
{
return _IsBalance(_root);
}
int Height()
{
return _Height(_root);
}
protected:
int _Height(Node* root)
{
if (root == NULL)
return 0;
int left = _Height(root->_left);
int right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
bool _IsBalance(Node* root)
{
if (root == NULL)
return true;
int left = _Height(root->_left);
int right = _Height(root->_right);
if (left-right != root->_bf)
{
cout << "平衡因子錯誤，不平衡" << root->_key << endl;
return false;
}
return abs(left - right)<2&&_IsBalance(root->_left) && _IsBalance(root->_right);
}
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
void RotateL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
if (ppNode == NULL)
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
subR->_bf = parent->_bf = 0;
}
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
Node* ppNode = parent->_parent;
subL->_right = parent;
parent->_parent = subL;
if (ppNode == NULL)
{
_root = subL;
subL->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
subL->_parent = ppNode;
}
subL->_bf = parent->_bf = 0;
}
void RotateLR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
int bf = subLR->_bf;
RotateL(parent->_left);
RotateR(parent);
if (bf == 1)
{
parent->_bf = -1;
subL->_bf = 0;
}
else if (bf == -1)
{
subL->_bf = 1;
parent->_bf = 0;
}
else
subL->_bf = parent->_bf = 0;
}
void RotateRL(Node* parent)
{
Node* subR = parent->_right;
Node* subRL = subR->_left;
int bf = subRL->_bf;
RotateR(parent->_right);
RotateL(parent);
if (bf == 1)
{
parent->_bf = 0;
subR->_bf = -1;
}
else if (bf == -1)
{
subR->_bf = 0;
parent->_bf = 1;
}
else
subR->_bf = parent->_bf = 0;
}
private:
Node* _root;
};
void Test1()
{
AVLTree<int, int> t;
int a[]={16, 3, 7, 11, 9, 26, 18, 14, 15};
for (int i = 0; i < sizeof(a) / sizeof(a[0]); ++i)
{
t.Insert(a[i], i);
}
t.InOrder();
t.IsBalance();
}
int main()
{
Test1();
system("pause");
return 0;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
