溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
AVL是平衡搜索二叉樹，它的主要特點在于：（1）左子樹和右子樹的高度差絕對值<1,（2）樹中的每個子樹都是AVL樹，（3）每個節點都有一個平衡因子（-1、0、1），平衡因子的大小等于右子樹的高度減左子樹的高度
下面就是一個AVL樹：
其中，這個樹滿足左子樹和右子樹的高度差絕對值小于1，每個節點的平衡因子都滿足條件。
下面是AVLTree中節點的結構：
template <class K, class V>
struct AVLTreeNode
{
K _key;
V _value;
int _bf; //節點的平衡因子
AVLTreeNode<K, V>* _parent; //指向節點的父節點
AVLTreeNode<K, V>* _left; //指向節點的左孩子
AVLTreeNode<K, V>* _right; //指向節點的右孩子
AVLTreeNode(const K& key = K(), const V& value = V()) //構造節點
:_key(key)
, _value(value)
, _parent(NULL)
, _left(NULL)
, _right(NULL)
, _bf(0)
{ }
};下面討論一下AVLTree中插入節點的情況：
當插入一個節點時，如果這個節點的父節點的平衡因子不滿足AVLTree的特點，這時就需要對AVLTree進行調整，直到滿足AVLTree的條件。
（1）左單旋
（2）右單旋
（3）左右雙旋
（4）右左雙旋
針對上面的情況，下面是具體的程序實現：
#pragma once
#include <assert.h>
#include <math.h>
//實現平衡搜索二叉樹
//構造AVL樹的節點（使用三叉鏈表）
template <class K, class V>
struct AVLTreeNode
{
K _key;
V _value;
int _bf;
AVLTreeNode<K, V>* _parent;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode(const K& key = K(), const V& value = V()) //構造節點
:_key(key)
, _value(value)
, _parent(NULL)
, _left(NULL)
, _right(NULL)
, _bf(0)
{ }
};
template <class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
AVLTree() //初始化根節點
:_root(NULL)
{ }
bool Insert(const K& key, const V& value) //插入
{
//根節點判空
if (_root == NULL)
{
_root = new Node(key, value);
return true;
}
//將數據先插入到樹中
Node* cur = _root;
Node* parent = NULL;
Node* tmp = new Node(key, value);
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
if (parent->_key > key)
{
parent->_left = tmp;
tmp->_parent = parent;
}
if (parent->_key < key)
{
parent->_right = tmp;
tmp->_parent = parent;
}
//對樹進行調整
cur = tmp;
parent = cur->_parent;
bool isRotate = false;
while (parent)
{
if (parent->_left == cur) //插入左節點，父親節點的平衡因子-1
{
parent->_bf--;
}
if (parent->_right == cur) //插入右節點，父親節點的平衡因子+1
{
parent->_bf++;
}
if (parent->_bf == 0)
//調整過程中，若碰到平衡因子為0的節點，就不用在繼續調整
{
break;
}
else if (parent->_bf == -1 || parent->_bf == 1) //更新平衡因子
{
cur = parent;
parent = cur->_parent;
}
else
{
if (parent->_bf == 2)
{
if (cur->_bf == 1) //左單旋
{
_RotateL(parent);
}
else //右左單旋
{
_RotateRL(parent);
}
}
else //=-2
{
if (cur->_bf == -1) //右單旋
{
_RotateR(parent);
}
else //左右單旋
{
_RotateLR(parent);
}
}
isRotate = true;
}
break;
}
if (isRotate)
{
if (parent->_parent == NULL)
{
_root = parent;
return true;
}
}
return true;
}
void InOrder() //后序遍歷
{
_InOrder(_root);
cout << endl;
}
bool IsBalance()
{
if (_root == NULL)
{
cout << "root is null!" << endl;
return false;
}
return _IsBalance(_root);
}
int Heigth()
{
int heigthTree = 0;
Node* cur = _root;
while (cur)
{
if (cur != NULL)
{
heigthTree++;
}
cur = cur->_left;
}
return _Heigth(_root, heigthTree, 0);
}
protected:
int _Heigth(Node* root, int heigthTree, int countNum)
{
if (root == NULL)
{
if (countNum > heigthTree)
{
heigthTree = countNum;
}
return heigthTree;
}
_Heigth(root->_left, heigthTree, countNum++);
_Heigth(root->_right, heigthTree, countNum++);
}
bool _IsBalance(Node* root)
{
int bf = root->_right->_bf - root->_right->_bf;
if (bf == 0 || bf == 1 || bf == -1)
{
return true;
}
else
{
return false;
}
_IsBalance(root->_left);
_IsBalance(root->_right);
}
void _RotateL(Node*& parent) //左單旋
{
Node* SubR = parent->_right; //新建兩個節點指針
Node* SubRL = SubR->_left;
parent->_right = SubRL; //進行調整
if (SubRL)
{
SubRL->_parent = parent;
}
SubR->_left = parent;
SubR->_parent = parent->_parent;
parent->_parent = SubR;
parent->_bf = SubR->_bf = 0; //更改引用計數
parent = SubR;
}
void _RotateR(Node*& parent) //右單旋
{
Node* SubL = parent->_left; //新建兩個節點指針
Node* SubLR = SubL->_right;
parent->_left = SubLR; //進行調整
if (SubLR)
{
SubLR->_parent = parent;
}
SubL->_right = parent;
SubL->_parent = parent->_parent;
parent->_parent = SubL;
parent->_bf = SubL->_bf = 0;
parent = SubL;
}
void _RotateRL(Node*& parent) //右左單旋
{
Node* pNode = parent;
Node* subRNode = parent->_right;
Node* subRLNode = subRNode->_left;
int bf = subRLNode->_bf;
_RotateR(parent->_right);
_RotateL(parent);
if (bf == -1)
{
subRNode->_bf = 0;
pNode->_bf = -1;
}
else if (bf == 1)
{
subRNode->_bf = 1;
pNode->_bf = 0;
}
else
{
subRNode->_bf = 0;
pNode->_bf = 0;
}
subRNode->_bf = 0;
}
void _RotateLR(Node*& parent) //左右單旋
{
Node* pNode = parent;
Node* subLNode = parent->_left;
Node* subLRNode = subLNode->_right;
int bf = subLRNode->_bf;
_RotateL(parent->_left);
_RotateR(parent);
if (bf == -1)
{
subLNode->_bf = 0;
pNode->_bf = 1;
}
else if (bf == 1)
{
subLNode->_bf = -1;
pNode->_bf = 0;
}
else
{
subLNode->_bf = 0;
pNode->_bf = 0;
}
subLNode->_bf = 0;
}
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
protected:
Node* _root;
};
void Test()
{
AVLTree<int, int> ht;
/*ht.Insert(16, 1);
ht.Insert(3, 1);
ht.Insert(7, 1);
ht.Insert(11, 1);
ht.Insert(9, 1);
ht.Insert(26, 1);
ht.Insert(18, 1);
ht.Insert(14, 1);
ht.Insert(15, 1);*/
ht.Insert(4, 1);
ht.Insert(2, 1);
ht.Insert(6, 1);
ht.Insert(1, 1);
ht.Insert(3, 1);
ht.Insert(5, 1);
ht.Insert(15, 1);
ht.Insert(7, 1);
ht.Insert(16, 1);
ht.Insert(14, 1);
ht.InOrder();
cout<<ht.IsBalance()<<endl;
cout << ht.Heigth() << endl;
}免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
