黑客怎么攻击网站百度搜索优化关键词排名

AVL树的概念：一颗AVL树要么是空树要么就是满足一下条件的二叉搜索树：
1）它的左右子树都是AVL树；
2）左子树与右子树高度之差的绝对值不超过1；

这里的左子树与右子树高度之差称为平衡因子。

以下是定义结点：

template<class K,class V>struct AVLTreeNode
{AVLTreeNode(const K& k,const V& v): _pleft(NULL),_pright(NULL),_pParent(NULL), _key(k),_value(v),_bf(0)    //平衡因子{}AVLTreeNode<K,V>*  _pleft;AVLTreeNode<K,V>*  _pright;AVLTreeNode<K,V>*  _pParent;    //双亲K _key;V _value;int _bf;    //平衡因子
};

以下是AVL树类的实现：

template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K,V> Node;
public:AVLTree():_pRoot(NULL){}/*AVLTree(Node* pRoot):_pRoot(pRoot){}*/Node * Rotatel(Node* pRoot){_Rotatel(pRoot);}Node * Lotatel(Node* pRoot){_Lotatel(pRoot);}void Insert(const K &key, const V &value){_InsertNor(_pRoot, key, value);}void InOrder(){_InOrder(_pRoot);cout<<endl;}bool IsBalance(){return _IsBalance(_pRoot);}size_t Height(){return _Height(_pRoot);}

以下是四个旋转函数：
1）左单旋

private:void _Rotatel(Node* parent)  //左单旋{Node* pSubR=parent->_pright;Node* pSubRL=pSubR->_pleft;Node * pPParent=parent->_pParent;parent->_pright=pSubRL;if(pSubRL)pSubRL->_pParent=parent;pSubR->_pleft =parent;parent->_pParent=pSubR;pSubR->_pParent=pPParent;if(NULL==pPParent){_pRoot=pSubR ;pSubR->_pParent = NULL;}else{if(pPParent->_pleft==parent)pPParent->_pleft=pSubR;elsepPParent->_pright=pSubR;//pSubR->_pParent = pPParent;}parent ->_bf=pSubR->_bf==0;//parent = pSubR;}

2）右单旋

void _RotateR(Node* parent)//右单旋{Node *pSubL = parent->_pleft;Node *pSubLR = pSubL->_pright;Node *ppParent = parent->_pParent;parent->_pleft = pSubLR;if (pSubLR)pSubLR->_pParent = parent;pSubL->_pright = parent;parent->_pParent = pSubL;if (NULL == ppParent){_pRoot = pSubL;pSubL->_pParent = NULL;}else{if (parent == ppParent->_pleft)ppParent->_pleft = pSubL;elseppParent->_pright = pSubL;pSubL->_pParent = ppParent;}pSubL->_bf = parent->_bf = 0;parent = pSubL;}

3）先左后右双旋

    void _RotateLR(Node* pParent){Node *pSubL = pParent->_pleft;Node *pSubLR = pSubL->_pright;_Rotatel(pParent->_pleft);_RotateR(pParent);if (-1 == pSubLR->_bf)pParent->_bf = 1;else if (1 == pSubLR->_bf)pSubL->_bf = -1;}

4）先右后左双旋

void _RotateRL(Node* pParent){Node *pSubR = pParent->_pright;Node *pSubRL = pSubR->_pleft;_RotateR(pParent ->_pright);_Rotatel(pParent);if (1 ==  pSubRL->_bf)pParent->_bf = -1;else if (-1 ==  pSubRL->_bf)pSubR->_bf = 1;}

判断这棵树是否为平衡树：

    bool _IsBalance(Node* pRoot){if (pRoot == NULL)return true;int leftHeight = _Height(pRoot->_pleft);int rightHeight = _Height(pRoot->_pright);if (rightHeight - leftHeight != pRoot->_bf){cout << "平衡因子" << endl;return false;}return (abs(leftHeight - rightHeight) <2)&&_IsBalance(pRoot->_pleft)&&_IsBalance(pRoot->_pright);}

以下是插入函数：

    bool _Insert(Node* &pRoot,const K& key,const V& value){ if(pRoot==NULL){ pRoot=new Node(key,value);return true;}else{if(key < pRoot->_key){return _Insert(pRoot->_pleft, key, value);}else if(key > pRoot->_key){return _Insert(pRoot->_pright, key, value);}elsereturn false;}}bool _InsertNor(Node* &pRoot,const K& key,const V& value){if (NULL == pRoot){_pRoot = new Node(key, value);return true;}Node *pCur = pRoot;Node *parent = NULL;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;elseparent->_pright = pCur;pCur->_pParent = parent;if (pCur == parent->_pleft)--parent->_bf;else++parent->_bf;while (nullptr != parent){if (0==parent->_bf)return true;else if (1 == parent->_bf || -1 == parent->_bf){Node *ppParent = parent->_pParent;if (nullptr != ppParent){if (ppParent->_pleft == parent)ppParent->_bf--;elseppParent->_bf++;}parent = parent->_pParent;}else{if (2 == parent->_bf){if (1 == parent->_pright->_bf)_Rotatel(parent);else_RotateRL(parent);}else{if (-1 == parent->_pleft->_bf)_RotateR(parent);else_RotateLR(parent);}break;}}return true;}

求树的高度：

    size_t _Height(Node* pRoot){if(pRoot==NULL)return  0;else if(NULL==pRoot->_pleft&&NULL==pRoot->_pright)return 1;else{if(_Height(pRoot->_pleft)>_Height(pRoot->_pright))return _Height(pRoot->_pleft)+1;elsereturn _Height(pRoot->_pright)+1;}}

中序遍历AVL树：

    void _InOrder(Node *pRoot){if(_pRoot){_InOrder(pRoot->_pleft);cout<<pRoot->_key<<" ";_InOrder(pRoot->_pright) ;}}

以下是测试代码：

void tree1(){int a[10] = { 3, 2, 1, 4, 5, 6, 7, 10, 9, 8 };AVLTree<int, int> T;for (int i = 0; i < sizeof(a) / sizeof(a[0]); i++)T.Insert(a[i], a[i]);//cout << T.IsBalance() << endl;//T.InOrder();}