本文共 3836 字，大约阅读时间需要 12 分钟。

template
   
    struct AVLTreeNode{
   	AVLTreeNode(const T& data = T())		: _pLeft(nullptr)		, _pRight(nullptr)		, _pParent(nullptr)		, _data(data)		, _bf(0)	{
   }	AVLTreeNode
    
     * _pLeft;	AVLTreeNode
     
      * _pRight;	AVLTreeNode
      
       * _pParent;	T _data;	int _bf;   // 节点的平衡因子};// AVL: 二叉搜索树 + 平衡因子的限制template
       
        class AVLTree{
   	typedef AVLTreeNode
        
          Node;public: AVLTree() : _pRoot(nullptr) { } // 在AVL树中插入值为data的节点 bool Insert(const T& data) { if (_pRoot == nullptr) { _pRoot = new Node(data); return true; } Node* pCur = _pRoot; Node* pParent = nullptr; while (pCur) { pParent = pCur; if (data < pCur->_data) { pCur = pCur->_pLeft; } else if (data > pCur->_data) { pCur = pCur->_pRight; } else return false; } pCur = new Node(data); if (data < pParent->_data) pParent->_pLeft = pCur; else pParent->_pRight = pCur; pCur->_pParent = pParent; while (pParent) { //更新pParent的平衡因子 if (pCur == pParent->_pLeft) pParent->_bf--; else pParent->_bf++; //判断是否需要继续更新 if (pParent->_bf == 0) break; else if (pParent->_bf == 1 || pParent->_bf == -1) { //继续向上更新 pCur = pParent; pParent = pCur->_pParent; } else { if (pParent->_bf == 2) { if (pCur->_bf == 1) RotateL(pParent); else RotateRL(pParent); } else { if (pCur->_bf == -1) RotateR(pParent); else RotateLR(pParent); } break; } } return true; } void InOrder() { _InOrder(_pRoot); } Node* LeftMost() { if (_pRoot == nullptr) return nullptr; Node* pCur = _pRoot; while (pCur->_pLeft) pCur = pCur->_pLeft; reutrn pCur; } Node* RightMost() { if (_pRoot == nullptr) return nullptr; Node* pCur = _pRoot; wihle(pCur->_pRight) pCur = pCur->_pRight; return pCur; } // AVL树的验证 bool IsAVLTree() { return _IsAVLTree(_pRoot); }private: // 根据AVL树的概念验证pRoot是否为有效的AVL树 bool _IsAVLTree(Node* pRoot) { if (_pRoot == nullptr) return true; int leftHeight = _Height(pRoot->_pLeft); int rightHeight = _Height(pRoot->_pRight); if (abs(rightHeight - leftHeight) > 1 || rightHeight - leftHeight != _pRoot->_bf) return false; return _IsAVLTree(pRoot->_pLeft) && _IsAVLTree(pRoot->_pRight); } size_t _Height(Node* pRoot) { if (nullpte == pRoot) return 0; size_t leftHeight = _Height(pRoot->_pLeft); size_t rightHeight = _Height(pRoot->_pRight); return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; } // 右单旋 void RotateR(Node* pParent) { Node* pSubL = pParent->_pLeft; Node* pSubLR = pSubL->_pRight; pParent->_pLeft = pSubLR; if (pSubLR) pSubLR->_pParent = pParent; pSubL->_pRight = pParent; // 更新pParent和pSubL的双亲 Node* pPParent = pParent->_pParent; pParent->_pParent = pSubL; pSubL->_pParent = pPParent; // 更新原pParent双亲的左||右指针域指向 if (pPParent == nullptr) { _pRoot = pSubL; } else { if (pParent == pPParent->_pLeft) pPParent->_pLeft = pSubL; else pPParent->_pRight = pSubL; } pParent->_bf == pSubL->_bf = 0; } // 左单旋 void RotateL(Node* pParent) { Node* pSubR = pParent->_pRight; Node* pSubRL = pSubR->_pLeft; pParent->_pRight = pSubRL; if (pSubRL) pSubRL->_pParent = pParent; pSubR->_pLeft = pParent; Node* pPParent = pParent->_pParent; pParent->_pParent = pSubR; pSubR->_pParent == pPParent; if (pPParent == nullptr) { _pRoot = pSubR; } else { if (pPParent->_pLeft = pParent) pPParent->_pLeft = pSubR; else pPParent->_pRight = pSubR; } pParent->_bf = pSubR->_bf = 0; } // 右左双旋 void RotateRL(Node* pParent) { Node* pSubR = pParent->_pRight; Node* pSubRL = pSubR->_pLeft; int bf = pSubRL->_bf; RotateR(pParent->_pRight); RotateL(pParent); if (bf == -1) pSubR->_bf = 1; else pParent->_bf = -1; } // 左右双旋 void RotateLR(Node* pParent) { Node* pSubL = pParent->_pLeft; Node* pSubLR = pSubL->_pRight; int bf = pSubLR->_bf; RotateL(pParent->_pLeft); RotateR(pParent); if (bf == -1) pParent->_bf = 1; else pSubL->_bf = -1; } void _InOrder(Node* pRoot) { if (pRoot) { _InOrder(pRoot->_pLeft); cout << pRoot->_data << " "; _InOrder(pRoot->_pRight); } }private: Node* _pRoot;};
        
       
      
     
    
   

转载地址：http://qxkuk.baihongyu.com/