微博营销技巧,企业网站建设营销优化方案,没有网站可以做淘宝客吗,做视频网站如何利用用户的弱点TreeMap和TreeSet的底层实现原理就是红黑树 一)AVL树: 1)必须是一棵搜索树:前提是二叉树#xff0c;任取一个节点#xff0c;它的左孩子的Key小于父亲节点的Key小于右孩子节点的Key#xff0c;中序遍历是有序的#xff0c;按照Key的大小进行排列#xff0c;高度平衡的二叉… TreeMap和TreeSet的底层实现原理就是红黑树 一)AVL树: 1)必须是一棵搜索树:前提是二叉树任取一个节点它的左孩子的Key小于父亲节点的Key小于右孩子节点的Key中序遍历是有序的按照Key的大小进行排列高度平衡的二叉搜索树他的左右子树都是二叉搜索树 AB C
甲 乙 丙 丁 我们在这里面得出一个结论: Key(甲)Key(B)Key(乙)Key(A)Key(丙)Key(C)Key(丁) 2)必须是一颗平衡树:任意树中的节点要求结点左子树的高度和结点右子树的高度差的绝对值不可以超过1左右子树的高度差不能超过1 平衡因子左子树的高度-右子树的高度我们在AVL树中任取一个节点他的平衡因子只能是-110 3)AVL树任意一颗以根节点的左右子树的高度差的绝对值不超过1所以AVL树尽量保证左树和右树的高度是一致的那么这个时候再次进行数据查找的时间复杂度就是O(logN) 4)当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度 二)AVL树的查找与插入:如果插入失败了那么只有一种情况那么就是当前我要插入的数值在原来的树中已经有了 随着节点的插入导致了平衡因子发生了变化所以我们要进行平衡因子的调节 1)如图所示在上面这张图中当我们想要插入10这个节点的时候parent此时指向的是9这个节点此时10插入到了9的右子树那么9的平衡因子此时parent的平衡因子是1但是只能证明当前这棵树已经平衡了还是需要进行向上调整 2)此时如果插入的数据是8.5那么此时插入到的位置是9的左边此时parent的平衡因子是-1此时也是只能证明当前这棵树平衡了还是需要继续向上调整的 3)但是如果此时我们进行插入的数据是7.5那么此时parent节点指向8这个位置成功插入7.5这个数据之后发现parent的平衡因子变成0此时就不需要向上调整了 当parent.bf2的时候说当前这棵树已经不平衡了说明此时右树高说明要降低右树的高度增加左树的高度所以要进行旋转 当parent.bf-2的时候说当前这棵树已经不平衡了说明此时左树高说明要降低左树的高度增加右树的高度所以要进行旋转 左旋说明右树高右旋说明左树高 一)parent节点的平衡因子是2current节点存储的平衡因子是1: 二)parent结点的平衡因子是2current的节点的平衡因子是-1; 三)parent结点存储的平衡因子是-2current存储结点的平衡因子是-1; 1)这个旋转也叫做右单旋除了修改指针的指向还有修改平衡因子右单旋就是自己变成左孩子的右孩子 2)但是代码写到这里面还是存在着一定问题可能当前的parent是上面某一棵树的左子树也有可能是某一棵树的右子树 3)最后修改各个节点的平衡因子 4)但是上面的所有情况都考虑得比较不错了但是最终的代码还是存在着一定的瑕疵 四)parent存储结点的平衡因子是-2current存储结点的平衡因子是1; 右单旋:(新节点插入较高左子树的右侧)
左旋——自己变为右孩子的左孩子右旋——自己变为左孩子的右孩子 在上面的代码中我们就成功地进行了右旋 左单旋:新节点插入较高右子树的右侧
左右双旋:新节点插入到较高左子树的右侧 解决方案:先针对parent的左子树进行左旋再根据parent结点进行右旋再进行更新平衡因子的变化 右左双旋:新节点插入到较高右子树的左侧
验证AVL树:中序遍历有序况且是平衡二叉树
