网站空间大小,徐老师在那个网站做发视频,h5软件制作工具app,商务网站建设流程个人主页#xff1a;仍有未知等待探索-CSDN博客 专题分栏#xff1a;C 目录 一、概念
二、平衡因子
三、操作
插入
旋转
左单旋
右单旋
左右双旋
右左双旋 一、概念
二叉平衡搜索树又称AVL树#xff0c;是一种特殊的二叉搜索树。一般的二叉搜索树在遇到数据有序时仍有未知等待探索-CSDN博客 专题分栏C 目录 一、概念
二、平衡因子
三、操作
插入
旋转
左单旋
右单旋
左右双旋
右左双旋 一、概念
二叉平衡搜索树又称AVL树是一种特殊的二叉搜索树。一般的二叉搜索树在遇到数据有序时查找的效率比较的低。 而二叉平衡搜索树为了防止有这种极端的情况出现其保证了任一节点的左右子树的高度差不超过1通过控制高度使查找的次数降低。
二、平衡因子
二叉平衡搜索树在对节点的结构进行定义的时候多添加了一个平衡因子的变量bf用来判断树是否是平衡的。 平衡因子 右子树的高度 - 左子树的高度 平衡因子的取值为 0、1、-1、2、-2 当平衡因子为2、-2的时候代表了这棵树需要进行调整。
三、操作
插入 插入的步骤就是这些。 为什么调节完平衡因子为1、-1的时候要向上进行调整
如果调节完平衡因子为1、-1则在没有调整的时候平衡因子为0。新增了一个结点之后高度发生了变化。以当前节点为根节点的子树的高度发生了变化则以当前节点为其中的一个节点的子树的高度也同样发生了变化所以需要进行调整。 旋转
对于要通过旋转进行调节平衡因子的情况不细分的话有4种左单旋、右单旋、左右双旋、右左双旋。 注意在进行旋转的时候对于每个节点的指针变化要特别的细心。 节点中有三个指针一个指向左孩子、一个指向右孩子、另外一个指向双亲。 旋转点进行旋转的一个基准点。就比如左单旋的话parent就是旋转点。 左单旋 左单旋变换subrl 变成 parent 的右子树parent 成为 subr 的左子树。 直接看图变换是不难但是写代码就会有很多的坑指针的变换。 // 左单旋
// 参数是图中的parent也称为旋转点
void RotateL(node* parent)
{node* subr parent-right;node* subrl subr-left;// subrl 成为 parent 的右子树 parent-right subrl;if (subrl)subrl-parent parent;subr-left parent;node* pparent parent-parent;parent-parent subr;if (_root ! parent){if (pparent-left parent){pparent-left subr;}else {pparent-right subr;}subr-parent pparent;}else{_root subr;subr-parent nullptr;}parent-bf subr-bf 0;
} 右单旋
如图是右单旋的情况。 右单旋的变换sublr 变成 parent 的左子树将parent 变成 subl 的右子树。 直接看图变换是不难但是写代码就会有很多的坑指针的变换。 // 右单旋
// parent 为旋转点
void RotateR(node* parent)
{node* subl parent-left;node* sublr subl-right;// sublr成为parent的左子树parent-left sublr;// 如果sublr是空的话不需要更新它的双亲结点因为空指针不能进行解引用if (sublr)sublr-parent parent;// parent成为subl的右子树subl-right parent;// 记录一下这个子树的根节点的双亲结点node* pparent parent-parent;// 更新parent的双亲节点parent-parent subl;// 判断该子树的根节点是不是整个子树的根节点// 不是的话也需要更新该子树的根节点的双亲结点if (_root ! parent){if (pparent-left parent){pparent-left subl;}else {pparent-right subl;}subl-parent pparent;}else{_root subl;subl-parent nullptr;}// 更新平衡因子parent-bf subl-bf 0;
}左右双旋 左右双旋的变换先以 subl 为旋转点进行左单旋然后再以 parent 为旋转点进行右单旋。 注意1、指针的变换 2、注意新的节点插入在 b 子树的左子树和右子树的时候平衡因子的变化。 // 左右双旋
// 传参传的节点还是parent
void RotateLR(node* parent)
{node* psubl parent-left;node* psublr psubl-right;// 记录之前的 sublr 节点的平衡因子int bf psublr-bf;// 先以 subl 为旋转点进行左单旋RotateL(parent-left);// 然后再以 parent 为旋转点进行右单旋RotateR(parent);// 在完成旋转调整平衡后在对该子树的平衡因子进行变换// 至于为什么平衡因子等于这些值可以去看看我画的图然后进行对比// 还是比较清楚的if (-1 bf){psubl-bf psublr-bf 0;parent-bf 1;}else if (1 bf){parent-bf psublr-bf 0;psubl-bf -1; }else if (0 bf) // 如果在旋转之前的平衡因子就是为0则调整完之后的平衡因子都是0{parent-bf psubl-bf psublr-bf 0;}else // 这种情况一般是没有的如果有则是你写的AVL树是有错误的{assert(false);}
} 右左双旋 右左双旋的变换先以 subr 为旋转点进行右单旋然后再以 parent 为旋转点进行左单旋。 注意1、指针的变换 2、注意新的节点插入在 c 子树的左子树和右子树的时候平衡因子的变化。 // 右左双旋
void RotateRL(node* parent)
{node* psubr parent-right;node* psubrl parent-left;int bf psubrl-bf;// 先以subr为旋转点进行右单旋RotateR(parent-right);// 再以parent为旋转点进行左单旋RotateL(parent);// 更新平衡因子if (1 bf){psubr-bf psubrl-bf 0;parent-bf -1;}else if (-1 bf){parent-bf psubrl-bf 0;psubr-bf 1;}else if (0 bf){parent-bf psubr-bf psubrl-bf 0;}else {assert(false);}
}
