有什么软件做短视频网站,分销系统开发公司,网站发布工具,做网站多少人目录
1.平衡因子
2.旋转
a.节点定义
b.插入
插入
平衡因子更新 旋转 左单旋
右单旋 右左双旋 左右双旋
3.AVL树的验证 1.平衡因子
我们知道搜索二叉树有缺陷#xff0c;就是不平衡#xff0c;比如下面的树 什么是搜索树的平衡#xff1f;就是每个节点的左右子树的…目录
1.平衡因子
2.旋转
a.节点定义
b.插入
插入
平衡因子更新 旋转 左单旋
右单旋 右左双旋 左右双旋
3.AVL树的验证 1.平衡因子
我们知道搜索二叉树有缺陷就是不平衡比如下面的树 什么是搜索树的平衡就是每个节点的左右子树的高度差不超过1称平衡的搜索树为AVL树 那我们怎么控制搜索树的平衡呢
给出了平衡因子每个节点的平衡因子节点右子树的高度-节点左子树的高度或者反过来我们用前面那种平衡因子[-1,1],当超出这个范围搜索树就不平衡了
树的平衡因子可以这样表示 2.旋转
a.节点定义
templateclass K,class V
class AVLNode
{
public:typedef AVLNodeK,V Node;AVLNode(const pairK,V kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_bf(0){}Node* _left;Node* _right;Node* _parent;pairK, V _kv;//库里面提供的结构体表示key和valueint _bf;//平衡因子}; b.插入
插入
左边小插左边右边大插右边
templateclass K,class V
class AVLTree
{
public:typedef AVLNodeK, V Node;bool insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);return true;}Node* cur _root;Node* parent nullptr;while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{return false;}}cur new Node(kv);if (parent-_kv .first kv.first){parent-_left cur;}else{parent-_right cur;}cur-_parent parent;//更新平衡因子//...............return true;}protected:
//........
private:Node* _rootnullptr
};
平衡因子更新
前面都好理解插入一个节点那插入节点后平衡因子怎么更新呢 //更新平衡因子while (parent){if (parent-_left cur){parent-_bf--;}else{parent-_bf;}if (parent-_bf 1 || parent-_bf -1){//继续更新parent parent-_parent;cur cur-_parent;}else if (parent-_bf 0){//已经平衡break;}else if (parent-_bf 2 || parent-_bf -2){//进行旋转//...........}else{assert(false);//有可能不会出现上面的情况出现大问题了立马断死}break;//直接跳出了} 旋转
有四种情况需要旋转 else if (parent-_bf 2 || parent-_bf -2){// 进行旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度if(parent-_bf2cur-_bf1){ }else if (parent-_bf 2 cur-_bf -1){}else if (parent-_bf -2 cur-_bf 1){}else if (parent-_bf -2 cur-_bf -1){}else{assert(false);//有可能不会出现上面的情况出现大问题了立马断死}}左单旋 代码怎么写呢
是不是感觉这样就链接上了其实不对的每个节点的父亲也要更新的
你以为又结束了吗 protected:void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)//有可能subRL是空subRL-_parent parent;//记录父亲的父亲节点Node* pparent parent-_parent;subR-_left parent;parent-_parent subR;if (pparent nullptr){_root subR;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}//更新平衡因子parent-_bf subR-_bf 0; } 总结更新节点指向是一定要更新他的父亲节点的指向
右单旋
和左单旋是类似的读者可以模仿上面来分析自己把它写出来 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subR-_right;parent-_left subLR;if (subLR) //有可能subLR是空subLR-_parent parent;//记录父亲的父亲节点Node* pparent parent-_parent;subL-_right parent;parent-_parent subL;if (pparent nullptr){_root subL;_root-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}//更新平衡因子parent-_bf subL-_bf 0;} 右左双旋 代码怎么写呢
我们可以对单旋进行复用 这样就可以了吗不是单旋会把平衡因子都置为0所以还要更新平衡因子 void RotateRL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;//记录平衡因子int bf subRL-_bf;RotateR(parent-_right);RotateL(parent);//更新平衡因子if (bf 1){subRL-_bf 0;subR-_bf 0;parent-_bf -1;}else if (bf -1){subRL-_bf 0;subR-_bf 1;parent-_bf 0;}else if (bf 0){subRL-_bf 0;subR-_bf 0;parent-_bf 0;}else{assert(false);}} 左右双旋
类似的读者自行分析 void RotateLR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;int bf subLR-_bf;RotateL(parent-_left);RotateR(parent);if (bf 1){parent-_bf 0;subLR-_bf 0;subL-_bf -1;}else if (bf -1){parent-_bf 1;subLR-_bf 0;subL-_bf 0;}else if (bf 0){parent-_bf 0;subLR-_bf 0;subL-_bf 0;}else{assert(false);}}
else if (parent-_bf 2 || parent-_bf -2){// 进行旋转处理 -- 1、让这颗子树平衡 2、降低这颗子树的高度if(parent-_bf2cur-_bf1){ RotateL(parent);}else if (parent-_bf 2 cur-_bf -1){RotateRL(parent);}else if (parent-_bf -2 cur-_bf 1){RotateLR(parent);}else if (parent-_bf -2 cur-_bf -1){RotateR(parent);}else{assert(false);//有可能不会出现上面的情况出现大问题了立马断死}break;//直接跳出}
3.AVL树的验证
AVL树是在二叉搜索树的基础上加入了平衡性的限制因此要验证AVL树可以分两步1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列就说明为二叉搜索树2. 验证其为平衡树 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确
第一点很简单啦
void Inorder(){_Inorder(_root);cout endl;}
void _Inorder(Node* root){if (root nullptr){return;}_Inorder(root-_left);cout root-_kv.first ;_Inorder(root-_right);}
怎么验证平衡树呢 bool Isbalance(){return _Isbalance(_root);}bool _Isbalance(Node* root){if (root nullptr)return true;int leftH _Height(root-_left);int rightH _Height(root-_right);//用于快速判断哪个节点错误if (rightH - leftH ! root-_bf){cout root-_kv.first 节点平衡因子异常 endl;return false;}//不只检查本节点左右子树的平衡其他节点的子树也要检查return abs(leftH - rightH) 2 _Isbalance(root-_left) _Isbalance(root-_right);}int Height(){return _Height(_root);}int _Height(Node* root){if (root nullptr){return 0;}int leftH _Height(root-_left);int rightH _Height(root-_right);return leftH rightH ? leftH 1 : rightH 1;}
你们可以用这两个用例
void testAVLtree1()
{/*int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16,14 };*/int a[] { 16, 3, 7, 11, 9, 26, 18, 14, 15 };AVLTreeint, int av;for (auto e : a){if (e 14){int a 0;}av.Insert(make_pair(e, e));}av.Inorder();cout av.Isbalance()endl;
}
也要用随机数验证
void testAVLtree2()
{srand(time(0));const size_t N 500000;AVLTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));//cout t.IsBalance() endl;}//t.Inorder();cout t.Isbalance() endl;cout t.Height() endl;
}这两个都过了说明你的树就没问题了
