目录
AVL树的插入(包含更新平衡因子)
子树的旋转
子树的左旋转
子树的右旋转
左右双旋
右左双旋
求树的高度
判断是否为平衡二叉树
层序遍历
代码总览
AVL树的插入(包含更新平衡因子)
bool Insert(const pair& kv)
{
//1.搜索树的规则插入
//2.看是是否违反平衡规则,如果违反就需要处理:旋转
if (_root == nullptr)
{
_root = new Node(kv);
_root->_bf = 0;
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if(cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if(cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
cur->_parent = parent;
//...
//更新平衡因子
while (parent)//最远要更新根
{
if (cur == parent->_right)
{
parent->_bf++;
}
else
{
parent->_bf--;
}
//是否继续更新?
if (parent->_bf == 0)//1 or -1 ->插入节点填上了矮的那边
{
//高度不变,更新结束
break;
}
else if(parent->_bf == 1 || parent->_bf == -1)//0 -> 1 or -1插入节点导致一边变高了
{
//子树的高度变了,继续更新祖先
cur = cur->_parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
//-1 or 1 -> 2or-2 插入节点导致一边变高了
{
//子树不平衡 -- 需要旋转处理
//...
if (parent->_bf == 2 && cur->_bf == 1)//左单旋
{
RotateL(parent);
}
else if (parent->_bf == 2 && cur->_bf == 1)//右单选
{
RotateR(parent);
}
else if (parent->_bf == -2 && cur->_bf == -1)//左右双旋
{
RotateLR(parent);
}
else if (parent->_bf == 2 && cur->_bf == -1)//右左双旋
{
RotateRL(parent);
}
break;
}
else
{
//插入之前AVL树就存在不平衡子树,平衡因子的绝对值>=2的节点
assert(false);
}
}
return true;
}
子树的旋转
子树的左旋转
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 (parent == _root) { _root = subR; _root->_parent = nullptr; } else { if (parent == ppNode->_left) { ppNode->_left = subR; } else { ppNode->_right = subR; } subR->_parent = ppNode; } //更新平衡因子 parent->_bf = 0; subR->_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 (parent == _root) { _root = subL; _root->_parent = nullptr; } else { if (parent == ppNode->_left) { ppNode->_left = subL; } else { ppNode->_right = subL; } subL->_parent = ppNode; } //更新平衡因子 parent->_bf = 0; subL->_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 == 0) { parent->_bf = 0; subL->_bf = 0; subLR->_bf = 0; } else if (bf == 1) { parent->_bf = 0; subL->_bf = -1; subLR->_bf = 0; } else if(bf == -1) { parent->_bf = 1; subL->_bf = 0; subLR->_bf = 0; } else { //subLR->_bf旋转前就有问题 assert(false); } }
右左双旋
void RotateRL(Node* parent) { Node* subR = parent->_right; Node* subRL = subR->_left; int bf = subRL->_bf; RotateR(parent->_right); RotateL(parent); if (bf == 0) { subRL->_bf = 0; parent->_bf = 0; subR->_bf = 0; } else if (bf == 1) { subRL->_bf = 0; parent->_bf = -1; subR->_bf = 0; } else if (bf == -1) { subRL->_bf = 0; parent->_bf = 0; subRL->_bf = 1; } else { //subLR->_bf旋转前就有问题 assert(false); } }
求树的高度
int _Height(Node* root)
{
if (root == nullptr)
return 0;
int lh = _Height(root->_left);
int rh = _Height(root->_right);
return lh > rh ? lh + 1 : rh + 1;
}
int Height()
{
return _Height(_root);
}
判断是否为平衡二叉树
bool _IsBalanceTree(Node* root)
{
// 空树也是AVL树
if (nullptr == root)
return true;
// 计算pRoot节点的平衡因子:即pRoot左右子树的高度差
int leftHeight = _Height(root->_left);
int rightHeight = _Height(root->_right);
int diff = rightHeight - leftHeight;
// 如果计算出的平衡因子与pRoot的平衡因子不相等,或者
// pRoot平衡因子的绝对值超过1,则一定不是AVL树
if (abs(diff) >= 2)
{
cout << root->_kv.first << "节点平衡因子异常" << endl;
return false;
}
if (diff != root->_bf)
{
cout << root->_kv.first << "节点平衡因子不符合实际" << endl;
return false;
}
// pRoot的左和右如果都是AVL树,则该树一定是AVL树
return _IsBalanceTree(root->_left)
&& _IsBalanceTree(root->_right);
}
bool IsBalanceTree()
{
return _IsBalanceTree(_root);
}
层序遍历
vector> levelOrder() {
vector> vv;
if (_root == nullptr)
return vv;
queueq;
int levelSize = 1;
q.push(_root);
while (!q.empty())
{
// levelSize控制一层一层出
vector levelV;
while (levelSize--)
{
Node* front = q.front();
q.pop();
levelV.push_back(front->_kv.first);
if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);
}
vv.push_back(levelV);
for (auto e : levelV)
{
cout << e << " ";
}
cout << endl;
// 上一层出完,下一层就都进队列
levelSize = q.size();
}
return vv;
}
vector> levelOrder() { vector > vv; if (_root == nullptr) return vv; queue q; int levelSize = 1; q.push(_root); while (!q.empty()) { // levelSize控制一层一层出 vector levelV; while (levelSize--) { Node* front = q.front(); q.pop(); levelV.push_back(front->_kv.first); if (front->_left) q.push(front->_left); if (front->_right) q.push(front->_right); } vv.push_back(levelV); for (auto e : levelV) { cout << e << " "; } cout << endl; // 上一层出完,下一层就都进队列 levelSize = q.size(); } return vv; }