这篇文章将为大家详细讲解有关AVL树中如何插入，小编觉得挺实用的，因此分享给大家做个参考，希望大家阅读完这篇文章后可以有所收获。
创新互联公司长期为上千余家客户提供的网站建设服务，团队从业经验10年，关注不同地域、不同群体，并针对不同对象提供差异化的产品和服务；打造开放共赢平台，与合作伙伴共同营造健康的互联网生态环境。为荣昌企业提供专业的成都做网站、成都网站制作，荣昌网站改版等技术服务。拥有十多年丰富建站经验和众多成功案例,为您定制开发。
AVL树被称为高度平衡的二叉搜索树，尽量降低二叉树的高度，来保持二叉树的平衡，减少树的平均搜索长度。
AVL树的性质：1、左子树和右子树的高度之差（绝对值）不超过1
2、树中的每棵子树都是AVL树，
3、每个节点都有一个平衡因子，取值为（-1,0,1），通过平衡因子来判断树的平衡。
AVL树的插入需要考虑以下的几种情况：（箭头表示要插入的方向和节点）
第一种情况：插入的节点在20的右边，但是这样导致10的平衡因子大于1所以需要进行旋转才能改变平衡因子
第二种情况：在左边插入，导致平衡因子也不满足条件，需要旋转
第三种情况：插入的节点可能不构成单旋，所以需要双旋来解决
第四种情况：与第三种情况相反的双旋
如此通过旋转就可以达到在插入的时候让此二叉树达到平衡。
实现代码如下：
//main函数
#define _CRT_SECURE_NO_WARNINGS 1
#include
#include
using namespace std;
#include"AVLTree.h"
int main()
{
testAVLTree();
system("pause");
return 0;
}
//AVLTree ----> 被称为高度平衡的二叉搜索树
//使用三叉链来实现此二叉平衡搜索树
//性质：左右高度差不超过1 && 该树的左右子树都为二叉平衡树
template
struct AVLTreeNode
{
AVLTreeNode* _left;
AVLTreeNode* _right;
AVLTreeNode* _parent;
K _key;
V _value;
int _bf; // 平衡因子
//构造函数
AVLTreeNode(const K& key,const V& value) :_left(NULL), _right(NULL), _parent(NULL)
, _key(key), _value(value), _bf(0)
{}
};
template
class AVLTree
{
typedef AVLTreeNode Node;
public:
AVLTree() :_root(NULL)
{}
//使用非递归的插入
bool Insert(const K& key, const V& value)
{
//如果根节点不存在说明插入的节点是第一个节点，直接new 一个即可
if (_root == NULL){
_root = new Node(key, value);
return true;
}
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;
}
}
//走到这里，说明这个节点不存在，先new
cur = new Node(key, value);
//比较插入节点的值与父节点的值，再考虑链上左还是右
if (parent->_key < key){
parent->_right = cur;
cur->_parent = parent;
}
else if (parent->_key>key){
parent->_left = cur;
cur->_parent = parent;
}
else{
while (parent)
{
//判断cur是插在了parent的左边还是右边，再判断平衡因子是++还是--
if (cur == parent->_left){
parent->_bf--;
}
else{
parent->_bf++;
}
//++或--之后，判断平衡因子是否等于2或等于-2
if (parent->_bf == 0) //等于0说明没有变，则跳出循环
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = cur->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)//如果等于2或者等于-2则不再插入，先调节为二叉平衡树再插入
{
//根据平衡因子来判断需要调整的树是哪种类型，再选择单旋还是双旋
//如果父节点的平衡因子等于2，说明右子树比左子树高，再判断右子树的子树是在它的左边还是右边
if (parent->_bf == 2)
{
if (cur->_bf == 1){
RotateL(parent);
}
else{
RotateRL(parent);
}
}
else
{
if (cur->_bf == -1)
RotateR(parent);
else
RotateLR(parent);
}
}
}
}
return true;
}
//cur = parent;
//右单旋
void RotateR(Node* parent)
{
//需要记录parent上面是否还有父亲节点
Node* ppNode = parent->_parent;
Node* subL = parent->_left;
Node* subLR = subL->_right;
parent->_left = subLR;
//如果subLR存在 就将它的父亲置为parent
if (subLR)
subLR->_parent = parent;
subL->_right = parent;
parent->_parent = subL;
//如果parent等于根节点，说明已经到第一个节点，不需要调整，直接将subL作为根即可
if (parent == _root)
{
_root = subL;
subL->_parent = NULL;
}
else //如果还没有到根节点还需要判断parent是左还是右
{
if (ppNode->_left == parent)
ppNode->_left = subL;
else{
ppNode->_right = subL;
}
subL->_parent = ppNode;
}
}
//左单旋
void RotateL(Node* parent)
{
Node* ppNode = parent->_parent;
Node* subR = parent->_right;
Node* subRL = subR->_left;
parent->_right = subRL;
//判断subRL是否存在
if (subRL){
subRL->_parent = parent;
}
subR->_left = parent;
parent->_parent = subRL;
if (_root == parent)
{
_root = subR;
subR->_parent = NULL;
}
else
{
if (ppNode->_left == parent)
ppNode->_left = subR;
else
ppNode->_right = subR;
subR->_parent = ppNode;
}
}
//左右单旋
void RotateLR(Node* parent)
{
RotateL(parent->_right);
RotateR(parent);
}
//右左单旋
void RotateRL(Node* parent)
{
RotateR(parent->_left);
RotateL(parent);
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}
bool IsBalance()
{
return _IsBalance(_root);
}
bool _IsBalance(Node* root)
{
if (root == NULL)
return;
int leftheight = _Height(root->_left);
int rightheight = _Height(root->_right);
return abs(rightheight - leftheight) < 2 && _IsBalance(root->_left) && _IsBalance(root->_right);
}
size_t _Height(Node* root)
{
if (root == NULL)
return 0;
size_t left = _Height(root->_left);
size_t right = _Height(root->_right);
return left > right ? left + 1 : right + 1;
}
private:
Node* _root;
};
void testAVLTree()
{
AVLTree t;
int a[] = { 16,3,7,11,9,26,18,14,15};
for (int i = 0; i < (sizeof(a) / sizeof(a[0])); i++)
{
cout<关于“AVL树中如何插入”这篇文章就分享到这里了，希望以上内容可以对大家有一定的帮助，使各位可以学到更多知识，如果觉得文章不错，请把它分享出去让更多的人看到。
网页名称：AVL树中如何插入
地址分享：http://cdxtjz.com/article/gopdop.html
