一.了解项目功能
在本次项目中我们的目标是实现一个AVL树 : 提供的功能有:
- AVL树结点类的构造函数
- AVL树的构造函数
- AVL树的插入函数
- 插入时结点的左单旋
- 插入时结点的右单旋
- 插入时结点的左右双旋
- 插入时结点的右左双旋
二.逐步实现项目功能模块及其逻辑详解
通过第二部分对项目功能的介绍，我们已经对 的功能有了大致的了解，虽然看似需要实现的功能很多，貌似一时间不知该如何下手，但我们可以分步分模块来分析这个项目的流程，最后再将各部分进行整合，所以大家不用担心，跟着我一步一步分析吧！
！！！注意，该部分的代码只是为了详细介绍某一部分的项目实现逻辑，故可能会删减一些与该部分不相关的代码以便大家理解，需要查看或拷贝完整详细代码的朋友可以移步本文第四部分。
实现AVLTreeNode类模板
构造AVLTreeNode类成员变量
构造AVLTreeNode类构造函数
代码语言：javascript复制//贴代码实现AVLTree类模板
构造AVLTree类成员变量
实现AVLTree类构造函数
实现AVLTree插入函数
实现AVLTree插入左单旋
实现AVLTree插入右单旋
实现AVLTree插入左右双旋
实现AVLTree插入右左双旋
由于我们要实现 的功能可以反复使用的逻辑，且至少在一开始执行一次,因此我们选择do...while的循环语句来实现这一部分的逻辑.
该部分功能实现代码如下:
代码语言：javascript复制//贴代码三.项目完整代码
我们将程序运行的代码分别在三个工程文件中编辑,完整代码如下:
test.c文件
代码语言：javascript复制#include"AVL_Tree.h"
int main()
{
int a[] = { 16,3,7,11,9,26,18,14,15 };
AVLTree<int, int> t;
for (auto e : a)
{
t.Insert(make_pair(e, e));
t.InOrder();
}
//1: 16
//2: 3 16
//3: 7 16(这步有错,7直接丢了),也就是说左右双旋错了
return 0;
}AVLTree.h文件
代码语言：javascript复制#pragma once
#include<iostream>
#include<assert.h>
using namespace std;
template<class K,class V>
struct AVLTreeNode
{
AVLTreeNode(const pair<K,V>& kv)
:_kv(kv)
,_left(nullptr)
,_right(nullptr)
,_parent(nullptr)
,_bf(0)
{}
pair<K, V> _kv;
AVLTreeNode<K,V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf;
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K,V> Node;
public:
AVLTree()
:_root(nullptr)
{}
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* cur = _root;
Node* parent = nullptr;
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->_left)//新增结点是parent的左孩子
{
parent->_bf--; //给parent的BF--.(因为这套代码逻辑是按照BF=右高-左高来写的)
}
else
{
parent->_bf ;
}
//当该结点的BF为0时,就不会再影响下一个父节点了,可以理解为:
//当你变为0时,你上一步的操作一定没有影响到你这整颗树的总高度,你的总高度不变,你就不会影响父节点的平衡因子
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
//继续向上迭代更新影响因子
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -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)
{
//右左双旋
RotateRL(parent);
}
else if (parent->_bf == -2 && cur->_bf == 1)
{
//左右双旋
RotateLR(parent);
}
break;//旋转结束,插入也就可以结束了
}
else
{
assert(false);
}
}
return true;
}
//左旋
void RotateL(Node* parent)
{
Node* cur = parent->_right;
Node* curleft = cur->_left;
Node* ppnode = parent->_parent;
//将失衡结点右孩子的左子树链接到失衡结点的右孩子
parent->_right = curleft;
if (curleft)
{
curleft->_parent = parent;
}
//将失衡结点连接到失衡结点右孩子的左孩子位置
parent->_parent = cur;
cur->_left = parent;
//处理父父结点的链接
cur->_parent = ppnode;
if (ppnode == nullptr)//为空代表parent就已经是root了
{
_root = cur;
}
else
{
if (ppnode->_left == parent)//失衡结点是其父节点的左孩子
{
ppnode->_left = cur;
}
else //失衡结点是其父节点的右孩子
{
ppnode->_right = cur;
}
}
//更新影响因子
parent->_bf = cur->_bf = 0;
}
//右单旋
void RotateR(Node* parent)
{
Node* cur = parent->_left;
Node* curright = cur->_right;
Node* ppnode = parent->_parent;
//将失衡结点左孩子的右子树连接到失衡结点的左孩子位置
parent->_left = curright;
if (curright)
{
curright->_parent = parent;
}
//将失衡结点连接到失衡结点左孩子的右孩子位置
parent->_parent = cur;
cur->_right = parent;
//链接父父结点
cur->_parent = ppnode;
if (ppnode == nullptr)//为空代表parent就已经是root了
{
_root = cur;
}
else
{
if (ppnode->_left == parent)
{
ppnode->_left = cur;
}
else
{
ppnode->_right = cur;
}
}
//更新影响因子
parent->_bf = cur->_bf = 0;
}
//右左双旋
void RotateRL(Node* parent)
{
//记录一下cur和cur->left指针的位置,因为双旋过后会找不到
Node* cur = parent->_right;
Node* curleft = cur->_left;
int curleft_bf = curleft->_bf;
RotateR(cur);
RotateL(parent);
//curleft_bf已经在上面两个函数里置0了,它无论哪种情况都是0我们不用管
//但还是处理一下,这样可以降低耦合度,防止单旋没改的情况
//处理平衡因子
if (curleft_bf == 1)
{
parent->_bf = -1;
cur->_bf = 0;
curleft->_bf = 0;
}
else if (curleft_bf == -1)
{
parent->_bf = 0;
cur->_bf = 1;
curleft->_bf = 0;
}
else if (curleft_bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curleft->_bf = 0;
}
else
{
assert(false);
}
}
//左右双旋
void RotateLR(Node* parent)
{
//记录一下cur和cur->right指针的位置,因为双旋过后会找不到
Node* cur = parent->_left;
Node* curright = cur->_right;
int curright_bf = curright->_bf;
RotateL(cur);
RotateR(parent);
//处理平衡因子
//curright_bf已经在上面两个函数里置0了,我们不用管
//但还是处理一下,这样可以降低耦合度,防止单旋没改的情况
if (curright_bf == -1)
{
parent->_bf = 1;
cur->_bf = 0;
curright->_bf = 0;
}
else if (curright_bf == 1)
{
parent->_bf = 0;
cur->_bf = -1;
curright->_bf = 0;
}
else if (curright_bf == 0)
{
parent->_bf = 0;
cur->_bf = 0;
curright->_bf = 0;
}
else
{
assert(false);
}
}
//中序遍历函数
void InOrder()
{
_InOrder(_root); //代替成员函数完成递归
cout << endl; //方便后续观察测试用例
}
private:
//中序遍历子递归函数
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left); //递归访问左子树
cout << root->_kv.first << " "; //访问根节点
_InOrder(root->_right); //递归访问右子树
}
Node* _root;
};结语
希望这篇 的实现详解能对大家有所帮助,欢迎大佬们留言或私信与我交流.
学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!
