鞍山建设信息网站,如何建设一个电商网站,3d设计房子的软件,python做网站是不是特别慢AVL树的插入
在向一棵本来高度平衡的AVL树中插入一个新节点时#xff0c;如果树中某个结点的平衡因子的绝对值 1#xff0c;则出现了不平衡。设新插入结点为P#xff0c;从结点P到根节点的路径上#xff0c;每个结点为根的子树的高度都可能增加1#xff0c;因此在每…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执行先左后右双旋转 具体代码
#includeiostream using namespace std; templateclass K, class V struct AVLTreeNode { AVLTreeNodeK, V* _pleft; AVLTreeNodeK, V* _pright; AVLTreeNodeK, 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) {} }; templateclass K, class V class AVLTree { typedef AVLTreeNodeK, V Node; public: AVLTree() :_pRoot(NULL) {} AVLTree(const AVLTreeK, V t); AVLTreeK, V operator(const AVLTreeK, 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() { AVLTreeint, 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; }
