#pragma once
#include
using namespace std;
#define NEG -1
#define ZERO 0
#define POS 1
template
struct AVLTreeNode//树的节点
{
K _key;
V _value;
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
int _bf;
AVLTreeNode(const K& key,const V& value)
:_key(key)
, _value(value)
, _left(NULL)
, _right(NULL)
, _parent(NULL)
, _bf(0)//平衡因子 取值 -1 0 1 （左高1 相等 右高1）
{}
};
template
class AVLTree
{
typedef AVLTreeNode Node;
public:
AVLTree()
:_root(NULL)
{}
~AVLTree(){}
bool Insert(const K& key,const V& value)//插入
{
if (_root == NULL)
{
_root = new Node(key,value);//空树 直接插入
return true;
}
Node* cur = _root, *prev = NULL;//当前 与 之前 节点指针
while (cur){
if (cur->_key < key)//插入key 比当前节点 key大 跳到右
{
if (cur->_right){//右不为空继续
prev = cur;
cur = cur->_right;
if (cur->_bf == ZERO)//如果节点的bf为0，说明插入（如果成功），会改变prev->bf的值
prev->_bf++;
}
else
{//如果右为空 到达插入节点位置，插入cur->bf ++
cur->_right = new Node(key,value);
cur->_right->_parent = cur;
cur->_bf++;
break;
}
}
else if (cur->_key>key)//同理 向左 插入
{
if (cur->_left){
prev = cur;
cur = cur->_left;
if (cur->_bf == ZERO)
prev->_bf--;
}
else
{
cur->_left = new Node(key, value);
cur->_left->_parent = cur;
cur->_bf--;
break;
}
}
else//key相等，插入失败，依次将改变的平衡因子 改回来
{
while (prev&&cur->_bf == ZERO)
{
if (prev->_left == cur)
prev->_bf++;
else
prev->_bf--;
cur = prev;
prev = prev->_parent;
}
return false;
}
}
//插入结束 对整棵树进行调节 使其继续平衡
//高度不变
if (cur->_bf == ZERO)
return true;
else//高度改变
{
//找高度变为-2 或 2的节点旋转
while (prev)
{
if (prev->_bf < -1)//左高2
{
if (cur->_bf <= -1)//右旋
{
_RotateR(prev);
cout << "右旋"<_bf > 1)//右高2
{
if (cur->_bf >= 1)//左旋
{
_RotateL(prev);
cout << "左旋" << endl;
break;
}
else//右左旋
{
_RotateR(cur);
_RotateL(prev);
cout << "右左旋" << endl;
break;
}
}
cur = prev;
prev = prev->_parent;
}
}
return true;
}
bool IsBalance()
{
if (_root == NULL)
return true;
return _Isbalance(_root);
}
Node* Find(const K& key)
{
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(const K& key)
{
if (_root == NULL)
{
return false;//空树删除失败
}
Node* cur = _root, *prev = NULL;
while (cur){
if (cur->_key < key)//删除位置在cur 右
{
if (cur->_right){//右非空，继续找
prev = cur;
cur = cur->_right;
}
else//右空，未找到删除节点 返回
return false;
}
else if (cur->_key>key)//删除位置在左
{
if (cur->_left){
prev = cur;
cur = cur->_left;
}
else
return false;
}
else
{
Node* parent = cur->_parent;//记录删除节点的 父
if (cur->_left == NULL)//删除节点 左空，直接使其右与prev相连
{
if (prev == NULL){//prev为空，删除根节点，根节点改变
_root = cur->_right;
delete cur;
return true;
}
if (prev->_right == cur){//prev右为cur，cur的右连到prev右
prev->_bf--;//平衡因子 减少
prev->_right = cur->_right;
if (cur->_right)
cur->_right->_parent = prev;
}
if (prev->_left == cur){//prev左为 cur
prev->_left = cur->_right;
prev->_bf++;
if (cur->_right)
cur->_right->_parent = prev;
}
delete cur;//释放节点
cur = prev;//将cur prev指向有效节点
prev = cur->_parent;
}
else if (cur->_right == NULL)//同上 cur右为空
{
if (prev == NULL){
_root = cur->_left;
delete cur;
return true;
}
if (prev->_right == cur){
prev->_bf--;
prev->_right = cur->_left;
if (cur->_left)
cur->_left->_parent = prev;
}
if (prev->_left == cur){
prev->_left = cur->_left;
prev->_bf++;
if (cur->_left)
cur->_left->_parent = prev;
}
delete cur;
cur = prev;
prev = cur->_parent;
}
else
{//cur左右都非空，为了避免换当前root的复杂操作，替换为删除cur左孩子 最右 节点 ，或者cur右孩子的 最左 节点，将其内容拷贝给cur
Node* tmp = cur;
prev = cur;
cur = cur->_right;
while (cur->_left)//找右树最左
{
prev = cur;
cur = cur->_left;
}
tmp->_key = cur->_key;
tmp->_value = cur->_value;//拷贝值
if (cur == prev->_left)//调节prev bf并将 cur右树连接到prev
prev->_bf++;
prev->_left = cur->_right;
}
if (cur == prev->_right)//同上
{
prev->_bf--;
prev->_right = cur->_right;
}
tmp = cur;//记录删除位置
cur = prev;
parent = cur;//cur prev 指向有效节点
prev = cur->_parent;
delete tmp;//删除tmp
}
while (prev &&cur->_bf == ZERO)//删除节点 父树高度可能改变，依次确认并修改 bf （cur bf为0 说明是 -1 或 1 变来 高度发生改变 需修改父节点 bf）
{
if (cur == prev->_left){
prev->_bf++;
}
if (cur == prev->_right)
{
prev->_bf--;
}
cur = prev;
prev = prev->_parent;
}
prev = parent;//prev指向 实际删除节点的父节点
if (prev->_bf < ZERO)
cur = prev->_left;
if (prev->_bf > ZERO)
cur = prev->_right;
if (prev->_bf == ZERO){
cur = prev;
prev = prev->_parent;
}
break;
}
}
//找高度变为-2 或 2的节点旋转
while (prev)
{
if (prev->_bf < -1)//左高2
{
cur = prev->_left;//因为删除一侧节点可能需要另一侧旋转，因此需要对 cur重新赋值
if (cur && (cur->_bf <= -1 || cur->_bf == ZERO))//右旋
{
_RotateR(prev);
if (prev->_left&&prev->_right == NULL)//判断旋转后 prev的bf
prev->_bf--;
cout << "右旋" << endl;
}
else//左右旋
{
_RotateL(cur);
_RotateR(prev);
cout << "左右旋" << endl;
}
cur = prev->_parent;
prev = cur->_parent;
while (prev&&cur->_bf == ZERO)//依次修改旋转完毕的prev的bf
{
if (cur == prev->_left)
prev->_bf++;
else
prev->_bf--;
cur = prev;
prev = prev->_parent;
}
}
else if (prev->_bf > 1)//右高2
{
cur = prev->_right;
if (cur && (cur->_bf >= 1 || cur->_bf == ZERO))//左旋
{
_RotateL(prev);
cout << "左旋" << endl;
if (prev->_right&&prev->_left == NULL)
prev->_bf++;
}
else//右左旋
{
_RotateR(cur);
_RotateL(prev);
cout << "右左旋" << endl;
}
cur = prev->_parent;
prev = cur->_parent;
while (prev&&cur->_bf == ZERO)
{
if (cur == prev->_left)
prev->_bf++;
else
prev->_bf--;
cur = prev;
prev = prev->_parent;
}
}
cur = prev;
if (prev)
prev = prev->_parent;
}
return true;
}
private:
Node* _root;
int _height(Node* root)
{
if (root == NULL)
return 0;
int left = 1, right =1;
left += _height(root->_left);
right += _height(root->_right);
return left > right ? left : right;
}
bool _Isbalance(Node* root)//判断 数是否平衡 bf是否匹配
{
if (root == NULL)
return true;
/*if (root ->_left==NULL&&root->_right==NULL)
return true;*/
bool left = _Isbalance(root->_left);
bool right = _Isbalance(root->_right);
int num1 = 1;
num1+=_height(root->_left);
int num2 = 1;
num2+=_height(root->_right);
if (left == false || right == false)
{
cout << "not balace!" << " key: " << root->_key << "bf: " << root->_bf << endl;
return false;
}
if (num2-num1!=root->_bf)
{
cout << "bf error!" << "key:" << root->_key << "bf: " << root->_bf << "a-b:" << num1-num2 << endl;
return false;
}
if (abs(num1-num2) <= 1)
return true;
return false;
}
//旋转后 bf 调节总结：左旋 bf 减小 右旋 bf 增加；sub=2 ，parent变化 3，sub变化 2；sub=1，parent 变化2，sub变化 1；
void _RotateR(Node* parent)//右旋
{
Node* subL = parent->_left;
Node* subLR = subL->_right;
Node* ppNode=parent->_parent;
subL->_right = parent;
parent->_parent = subL;
parent->_left = subLR;
if (subLR)
subLR->_parent = parent;
if (ppNode)
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else
ppNode->_right = subL;
}
else
_root = subL;
subL->_parent = ppNode;//旋转
//修改 bf
if (subL->_bf == -2){
parent->_bf = 1;
subL->_bf=0;
}
else
{
subL->_bf++;
parent->_bf = 0;
}
}
void _RotateL(Node* parent)//左旋
{
Node* subR= parent->_right;
Node* subRL = subR->_left;
Node* ppNode = parent->_parent;
subR->_left = parent;
parent->_parent = subR;
parent->_right = subRL;
if (subRL)
subRL->_parent = parent;
if (ppNode)
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
}
else
_root = subR;
subR->_parent = ppNode;//以上为左旋转
//以下下修改 bf 值
if (subR->_bf == 2)//右孩子的高度为2 说明旋转前 高度差在右孩子的下方，旋转后parent 右支 没有可以连接的，高度会降3 从2变为-1
{
parent->_bf = -1;
subR->_bf = 0;
}
else{ //右孩子高度为1，旋转后高度将2 buf为 0，而右孩子 高度将1；
parent->_bf = 0;
subR->_bf--;
}
}
};
文章名称：c++AVLTree(高度平衡的搜索二叉树)
浏览路径：
http://bzwzjz.com/article/jjcejh.html
