平衡二叉查找树插入节点操作( AVLTree )：旋转、调整平衡_avl插入一个新的节点导致失衡,重新调整后高度变化

AVL树的插入

在向一棵本来高度平衡的AVL树中插入一个新节点时，如果树中某个结点的平衡因子的绝对值 > 1，则出现了不平衡。设新插入结点为P，从结点P到根节点的路径上，每个结点为根的子树的高度都可能增加1，因此在每执行一次二叉搜索树的插入运算后，都需从新插入的结点P开始，沿该结点插入的路径向根节点方向回溯，修改各结点的平衡因子，调整整棵树的高度，恢复被破坏的平衡性质。

 

AVL树插入算法：

 

新节点P的平衡因子为0，但其双亲结点Pr的平衡因子有三种情况：

 

1、结点Pr的平衡因子为0

在Pr的较矮的子树上插入新节点，结点Pr平衡，其高度没有增加，此时从Pr到根路径上各结点为根的子树的高度不变，即各结点的平衡因子不变，结束平衡化处理。

 

2、结点Pr的平衡因子的绝对值为1；

插入前Pr的平衡因子为0，插入后以Pr为根的子树没有失去平衡，但该子树的高度增

加，需从该结点Pr向根节点方向回溯，继续查看Pr的双亲结点的平衡性。

 

3、结点Pr的平衡因子的绝对值为2

新节点在较高的子树插入，需要做平衡化处理：

若Pr = 2，说明右子树高，设Pr的右子树为q

当q的平衡因子为1，执行左单旋转

 

 

 

 

当q的平衡因子为-1，执行先右后左双旋转

 

 

 

若Pr = -2，说明左子树高，设Pr的左子树为q

当q的平衡因子为-1，执行右单旋转

 

当q的平衡因子为1，执行先左后右双旋转

 

具体代码：

#include<iostream>  

using namespace std;

template<class K, class V>

struct AVLTreeNode

{

AVLTreeNode<K, V>* _pleft;

AVLTreeNode<K, V>* _pright;

AVLTreeNode<K, V>* _pParent;

K _key;

V _value;

int _bf;

AVLTreeNode(const K& key, const V& value)

:_pleft(NULL)

, _pright(NULL)

,_pParent(NULL)

, _key(key)

,_value(value)

,_bf(0)

{}

};

template<class K, class V>

class AVLTree

{

typedef AVLTreeNode<K, V> Node;

public:

AVLTree()

:_pRoot(NULL)

{}

AVLTree(const AVLTree<K, V>& t);

AVLTree<K, V>& operator=(const AVLTree<K, V>& t);

~AVLTree()

{

_Destory(_pRoot);

}

public:

bool Insert(const K& key, const V& value)

{

if(NULL == _pRoot)

{

_pRoot = new Node(key, value);

return true;

}

//寻找插入位置

Node* parent = NULL;

Node* pCur = _pRoot;

while(pCur)

{

if(key < pCur->_key)

{

parent = pCur;

pCur = pCur->_pleft;

}

else if(key > pCur->_key)

{

parent = pCur;

pCur = pCur->_pright;

}

else

return false;

}

pCur = new Node(key, value);

//插入

if(key < parent->_key)

{

parent->_pleft = pCur;

}

else

{

parent->_pright = pCur;

}

pCur->_pParent = parent;

//更新平衡因子

while(parent)

{

if(parent->_pleft == pCur)

{

parent->_bf--;

}

else

{

parent->_bf++;

}

if(parent->_bf == 0)

{

break;

}

else if(1 == parent->_bf || parent->_bf == -1)

{

pCur = parent;

parent = pCur->_pParent;

}

else

{

if(parent->_bf == 2)

{

if(pCur->_bf == 1)

_RotateL(parent);

else if(pCur->_bf == -1)

_RotateRL(parent);

}

else if(parent->_bf == -2)

{

if(pCur->_bf == -1)

_RotateR(parent);

else if(pCur->_bf == 1)

_RotateLR(parent);

}

break;

}

}

return true;

}

void Inorder()     //中序遍历

{

_Inorder(_pRoot);

cout << endl;

}

bool IsBalance()    //判断是否平衡

{

int height = 0;

return _IsBalance(_pRoot, height);

}

private:

void _RotateR(Node* parent)

{

Node* subL = parent->_pleft;

Node* subLR = subL->_pright;

parent->_pleft = subLR;

if(subLR)

subLR->_pParent = parent;

subL->_pright = parent;

Node* pParent = parent->_pParent;

parent->_pParent = subL;

if(pParent == NULL)

{

_pRoot = subL;

subL->_pParent = NULL;

}

else

{

if(pParent->_pleft == parent)

{

pParent->_pleft = subL;

}

else

{

pParent->_pright = subL;

}

subL->_pParent = pParent;

}

subL->_bf = parent->_bf = 0;

}

void _RotateL(Node* parent)

{

Node* subR = parent->_pright;

Node* subRL = subR->_pleft;

parent->_pright = subRL;

if(subRL)

subRL->_pParent = parent;

subR->_pleft = parent;

Node* pParent = parent->_pParent;

parent->_pParent = subR;

if(pParent == NULL)

{

_pRoot = subR;

subR->_pParent = NULL;

}

else

{

if(pParent->_pleft == parent)

{

pParent->_pleft = subR;

}

else

{

pParent->_pright = subR;

}

subR->_pParent = pParent;

}

subR->_bf = parent->_bf = 0;

}

void _RotateRL(Node*& parent)

{

        Node* subR = parent->_pright;  

        Node* subRL = subR->_pleft;  

        _RotateR(subR);      

        _RotateL(parent);       

  

        int bf = subRL->_bf;  

  

        if (bf == 0)  

        {    

            subRL->_bf = parent->_bf = 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;  

            subR->_bf = 1;  

        } 

}

void _RotateLR(Node*& parent)

{

        Node* subL = parent->_pleft;  

        Node* subLR = subL->_pright;  

        _RotateL(subL);  

        _RotateR(parent);  

        int bf = subLR->_bf;  

  

        if (bf == 0)  

        {  

            subLR->_bf = parent->_bf = subL->_bf = 0;  

        }  

  

        else if (bf == 1)  

        {  

            subLR->_bf = 0;  

            parent->_bf = 1;  

            subL->_bf = 0;  

        }  

  

        else if (bf == -1)  

        {  

            subLR->_bf = 0;  

            parent->_bf = 0;  

            subL->_bf = -1;  

        }  

}

void _Destory(Node*& pRoot)

{

if (_pRoot == NULL)

return;

_Destory(pRoot->_pleft);

_Destory(pRoot->_pright);

delete pRoot;

pRoot = NULL;

}

protected:

void _Inorder(Node* pRoot)     //中序

{

if (pRoot == NULL)

{

return;

}

_Inorder(pRoot->_pleft);

cout << pRoot->_key << " ";

_Inorder(pRoot->_pright);

}

bool _IsBalance(Node* pRoot, int& height)

{

if (pRoot == NULL)

{

height = 0;

return true;

}

int left, right;

if (_IsBalance(pRoot->_pleft, left) && _IsBalance

(pRoot->_pright, right)

&& abs(right - left) < 2)

{

height = left > right ? left + 1 : right + 1;

if (pRoot->_bf != right - left)

{

cout << "平衡因子异常：" << pRoot->_key 

<< endl;

return false;

}

return true;

}

else

{

return false;

}

}

size_t _Height(Node* pRoot)    //高度

{

if (pRoot == NULL)

{

return 0;

}

int l = _Height(pRoot->_pleft);

int r = _Height(pRoot->_pright);

return l > r ? l + 1 : r + 1;

}

private:

Node* _pRoot;

};

int main()

{

AVLTree<int, int> t;

t.Insert(3,3);

t.Insert(7,7);

t.Insert(11,11);

t.Insert(14,14);

t.Insert(15,15);

t.Insert(18,18);

t.Insert(16,16);

t.Insert(26,26);

t.Insert(9,9);

t.Inorder();  

    cout << "IsBalance? " << t.IsBalance() << endl;  

system("pause");

return 0;

}