利用路由器做网站,做网站行业,网站如何实现临时聊天,怎么编辑网站内容前言
紧接着上一篇文章#xff0c;我们来模拟实现一下set的底层结构
引入
对于BSTree#xff0c;虽然可以缩短查找的效率#xff0c;但如果数据有序它将退化为单支树
我们可以用AVL树来解决这个问题。
概念
AVL树#xff1a;
它的每个结点的左右子树高度之差的绝对值…前言
紧接着上一篇文章我们来模拟实现一下set的底层结构
引入
对于BSTree虽然可以缩短查找的效率但如果数据有序它将退化为单支树
我们可以用AVL树来解决这个问题。
概念
AVL树
它的每个结点的左右子树高度之差的绝对值不超过1它的左右子树都是AVL树
对于10来说左右子树高度差为2所以不满足
实现
基本结构
templateclass K, class V
struct AVLTreeNode
{using Node AVLTreeNodeK, V;Node* _left; //左节点Node* _right; //右节点Node* _parent //父节点int _bf; //平衡因子//计算方式右树高度减去左树高度pairK, V _kv; //用pair封起来的键值对AVLTreeNode(const pairK, V kv):_kv(kv),_bf(0),_left(nullptr),_right(nullptr),_parent(nullptr){}
};插入
和搜索树的插入规则前半部分是相同的具体细节可以看注释 bool Insert(const pairK, V kv){//1.按照搜索树规则插入先找到合适的位置然后链接if (_root nullptr){_root new Node(kv);return true;}//如果树为空特殊判断Node* parent nullptr;//父节点//方便记录父节点原来的子树Node* cur _root;while (cur ! nullptr){if (cur-kv.first kv.first){parent cur;cur cur-_left;}else if (cur-kv.first kv.first){parent cur;cur cur-_right;}else{return false;}}//查找完再判断是父节点的左树还是右数//标记为Acur new Node(kv);if (parent-kv.first kv.first){parent-_right cur;}else{parent-_right cur;}cur-_parent parent;//2.更新平衡因子根据AVL的规则进行旋转调整// - 插入因子会影响自己所有的祖先节点// - 更新原则// 1.修改_bf// - cur是_parent左边_parent-_bf--// - cur是_parent右边_parent-_bf// 2.根据_parent-_bf是否为0来判断是否修改祖先的_bf// - _bf 0 在更新前_bf是-1或1更新后左右平衡了所以不会影响祖先// - _bf 1/-1 更新前平衡因子为0更新后左右不平衡了所以祖先也要更新// 3._bf 2/-2 插入后出现问题要进行旋转while(parent){if (parent-_right cur){parent-_bf;}else{parent-_bf--;}if (parent-_bf 0){break;}else if (parent-_bf 1 || parent-_bf 1){cur cur-_parent;parent parent-_parent;}else if (parent-_bf 2 || parent-_bf -2){if (parent-_bf 2 cur-_bf 1){RotateL(parent);}else if(parent-_bf -2 cur-_bf -1){RotateR(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else{RotateRL(parent);}break;//因为旋转完就是全都平衡了所以直接结束循环}else{throw(false);}}return true;}旋转
旋转也是插入的一部分只是因为比较重要所以单独拎出来写
变量说明
h表示树的高度a、b、c是树的名字3060是_value
左单旋 左单旋适合的情况 右树插入新的节点导致祖先节点不平衡
操作
将右节点的左子树变为祖先节点的右子树将祖先节点变为父节点的左子树
void RotateL(Node* parent) //右单旋
{Node* subR parent-_right; //subR是parent的右节点Node* subRL subR-_left; //subRL是subR的左节点parent-_right subRL;if (subRL){subRL-_parent parent;}subR-_left parent;parent-_parent subR;if (parent _root){_root subR;subR-_parent nullptr;}else{if (parent-_parent-_left parent){parent-_parent-_left subR;}else{parent-_parent-_right subR:}subR-_parent parent-_parent;}parent-_bf 0;subR-_bf 0;
}右单旋
和上面的逻辑相同只是新增节点放在了左子树要向右旋转 void RotateR(Node* parent) //右单旋{Node* subL parent-_left; //subL是parent的左节点Node* subLR subL-_right; //subLR是subL的右节点parent-_left subLR;if (subLR){subLR-_parent parent;}subL-_right parent;parent-_parent subL;if (parent _root){_root subL;subL-_parent nullptr;}else{if (parent-_parent-_left parent){parent-_parent-_left subL;}else{parent-_parent-_right subL:}subL-_parent parent-_parent;}parent-_bf 0;subL-_bf 0;}左右双旋
旋转的代码相同就是对于平衡因子的处理需要注意 分四种情况考虑 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf -1){subLR-_bf 0;subL-_bf 0;parent-_bf 1;}else if (bf 1){subLR-_bf 0;subL-_bf -1;parent-_bf 0;}else if (bf 0){subLR-_bf 0;subL-_bf 0;parent-_bf 0;}else{throw(false);}}
右左双旋 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;int bf subRL-_bf;RotateR(subR);RotateL(parent);subRL-_bf 0;if (bf 1){subR-_bf 0;parent-_bf -1;}else if (bf -1){parent-_bf 0;subR-_bf 1;}else{parent-_bf 0;subR-_bf 0;}}判断是否平衡
我们再写一个接口来判断给的树是否平衡 int _Height(Node* root){if (root nullptr){return 0;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);return leftHeight rightHeight ? leftHeight 1 : rightHeight 1;}bool _IsBlance(Node* root){if (root nullptr){return true;}int leftHeight Height(root-_left);int rightHeight Height(root-_right);if (abs(leftHeight - rightHeight) 2){throw(不平衡);}if (rightHeight - leftHeight ! root-_bf){throw(平衡因子异常);}return _IsBlance(root-_left) _IsBlance(root-_right);}优化求高度
我们可以发现这段代码还可以优化因为每一次的高度都是要重新求的有很多重复工作。
所以我们可以增加一个参数
bool _IsBlance(Node* root, int height);这样树的高度就会再函数调用结束后被传出来并且不用修改返回值 bool _IsBalance(Node* root, int height){if (root nullptr){height 0;return true;}int leftHeight 0, rightHeight 0;if (!_IsBalance(root-_left, leftHeight) || !_IsBalance(root-_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) 2){cout root-_kv.first不平衡 endl;return false;}if (rightHeight - leftHeight ! root-_bf){cout root-_kv.first 平衡因子异常 endl;return false;}height leftHeight rightHeight ? leftHeight 1 : rightHeight 1;return true;}bool IsBalance(){int height 0;return _IsBalance(_root, height);}
结语
AVL树比搜索树要更优秀但具体逻辑指旋转要更复杂希望对你有帮助
