AVL树二叉搜索树虽可以缩短查找的效率但如果数据有序或接近有序二叉搜索树将退化为单支树查找元素相当于在顺序表中搜索元素效率低下。因此两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年 发明了一种解决上述问题的方法当向二叉搜索树中插入新结点后如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)即可降低树的高度从而减少平均搜索长度。一棵AVL树或者是空树或者是具有以下性质的二叉搜索树它的左右子树都是AVL树左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)如果一棵二叉搜索树是高度平衡的它就是AVL树。如果它有n个结点其高度可保持在Olog2N搜索时间复杂度Olog2NAVL树节点的定义static class TreeNode{ public TreeNode left; public TreeNode right; public int value; public TreeNode parent; public int bf;//平衡因子 public TreeNode(int value){ this.valuevalue; } }比起二次搜索树多了一个平衡因子当前节点的平衡因子右子树高度-左子树的高度。但是不是每棵树都必须有平衡因子这只是其中的一种实现方式。AVL树的插入1.按照二叉搜索树的方式插入新节点、这里我们按照上篇文章二叉搜索树的方式进行插入TreeNode nodenew TreeNode(value); if(rootnull){ rootnode; return true; } TreeNode parentnull; TreeNode curroot; while(cur!null){ if(cur.valuevalue){ parentcur; curcur.right; } else if(cur.valuevalue){ return false; } else{ parentcur; curcur.left; } } //curnull if(parent.valuevalue){ parent.rightnode; } else{ parent.leftnode; } node.parentparent; curnode;2.调整节点的平衡因子首先是判断当前cur节点是parent的左孩子或者右孩子决定平衡因是右孩子左孩子--//先看cur是parent的左还是右 决定平衡因子是还是-- if(curparent.right){ //如果是右树 右树平衡因子 parent.bf; }else { //左树平衡因子-- parent.bf--; }然后我们再来判断parent节点的平衡因子等于几应该是有三种情况parent.bf0此时整科树已经平衡 parent.bf1或parent.bf-1此时继续向上调整除此之外parent.bf2 cur.bf1此时右树高度高于左树需要进行左旋private void roteleft(TreeNode parent){ TreeNode subRparent.right; TreeNode subRLsubR.left; parent.rightsubRL; subR.leftparent; if(subRL!null){ subRL.parentparent; } TreeNode pParentparent.parent; parent.parentsubR; if(parentroot){ rootsubR; root.parentnull; } else { if(pParent.leftparent){ pParent.leftsubR; }else{ pParent.rightsubR; } subR.parentpParent; } subR.bf0; parent.bf0; }parent.bf-2 cur.bf-1此时左树高度高于右树需要进行右旋private void rotateright(TreeNode parent){ TreeNode sublparent.left; TreeNode sublRsubl.right; parent.leftsublR; subl.rightparent; //有可能sublr为空 没有sublR if(sublR!null){ sublR.parentparent; } TreeNode pParentparent.parent; parent.parentsubl; //检查 当前parent是不是根节点 if(parentroot){ rootsubl; root.parentnull; } else { //不是根节点 if(pParent.leftparent){ pParent.leftsubl; } else{ pParent.rightsubl; } subl.parentpParent; } subl.bf0; parent.bf0; }parent.bf-2 cur.bf-1if(parent.bf0){ //已经平衡了 break; } else if(parent.bf1||parent.bf-1){ //继续向上判断 curparent; parentcur.parent; }else{ if(parent.bf2){ //右树高度高 if(cur.bf1){ } else{ //parent.bf-1 } } else { //parent.bf-2左树高度高 降低左树高度 if(cur.bf1){ //右旋 rotateright(parent); } else{ //parent.bf-1 } } //上诉代码走完已经平衡了 break; }AVL树的验证1.验证其为二叉搜索树如果中序遍历可得到一个有序的序列就说明为二叉搜索树2.验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确private int height(TreeNode root){ if(rootnull){ return 0; } int lefthheight(root.left); int righthheight(root.right); return lefthrighth?lefth1:righth1; } public boolean isbalance(TreeNode root){ if(rootnull){ return true; } int leftheight(root.left); int rightheight(root.right); if(Math.abs(left-right)! root.bf){ return false; } return Math.abs(left-right)1 isbalance(root.left) isbalance(root.right); }AVL树是一棵绝对平衡的二叉搜索树其要求每个节点的左右子树高度差的绝对值都不超过1这样可以保证查询时高效的时间复杂度即 logn2。但是如果要对AVL树做一些结构修改的操作性能非常低下比如插入时要 维护其绝对平衡旋转的次数比较多更差的是在删除时有可能一直要让旋转持续到根的位置。因此如果需要一种查询高效且有序的数据结构而且数据的个数为静态的(即不会改变)可以考虑AVL树但一个结构经常修改就不太适合。红黑树红黑树概念红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。红黑树的性质1.最长路径做多是最短路径的2倍2.每个结点不是红色就是黑色3.根节点是黑色的4.如果一个节点是红色的则它的两个孩子结点是黑色的【没有2个连续的红色节点】5.对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点6.每个叶子结点都是黑色的(此处的叶子结点指的是空结点)满足以上性质红黑树能保证最长路径 ≤ 最短路径 × 2高度依然是O(log₂N)。class RBTreeNode{ RBTreeNode left null; RBTreeNode right null; RBTreeNode parent null; COLOR color RED; // 节点的颜色 int val; public RBTreeNode(int val){ this.val val; } }红黑树的插入红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步 1.按照二叉搜索的树规则插入新节点2.检测新节点插入后红黑树的性质是否造到破坏因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连在一起的红色节点此时需要对 红黑树分情况来讨论情况一:约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点cur为红p为红g为黑u存在且为红if(null ! uncle uncle.color COLOR.RED){ // 情况一叔叔节点存在且为红, // 解决方式将叔叔和双亲节点改为黑色祖父节点改为红色 // 如果祖父的双亲节点的颜色是红色需要继续往上调整 parent.color COLOR.BLACK; uncle.color COLOR.BLACK; grandFather.color COLOR.RED; cur grandFather; parent cur.parent; }情况二:cur为红p为红g为黑u不存在/u为黑{ // 情况二和情况三 // 叔叔节点不存在 || 叔叔节点存在但是颜色是黑色 if(cur parent.right) { // 情况三 rotateLeft(parent); RBTreeNode temp parent; parent cur; cur temp; }p为g的左孩子cur为p的左孩子则进行右单旋转相反p为g的右孩子cur为p的右孩子则进行左单旋转p、g变色--p变黑g变红情况三:cur为红p为红g为黑u不存在/u为黑p为g的左孩子cur为p的右孩子则针对p做左单旋转相反p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2// 情况二 rotateRight(grandFather); parent.color COLOR.BLACK; grandFather.color COLOR.RED;// 颜色枚举 enum Color { RED, BLACK } class RBTreeNode { int val; Color color; RBTreeNode left; RBTreeNode right; RBTreeNode parent; public RBTreeNode(int val) { this.val val; this.color Color.RED; // 新节点默认红色 } } class RBTree { private RBTreeNode root; // 左单旋 private void rotateLeft(RBTreeNode parent) { RBTreeNode subR parent.right; RBTreeNode subRL subR.left; parent.right subRL; if (subRL ! null) subRL.parent parent; subR.left parent; subR.parent parent.parent; parent.parent subR; if (subR.parent null) root subR; else if (subR.parent.left parent) subR.parent.left subR; else subR.parent.right subR; } // 右单旋 private void rotateRight(RBTreeNode parent) { RBTreeNode subL parent.left; RBTreeNode subLR subL.right; parent.left subLR; if (subLR ! null) subLR.parent parent; subL.right parent; subL.parent parent.parent; parent.parent subL; if (subL.parent null) root subL; else if (subL.parent.left parent) subL.parent.left subL; else subL.parent.right subL; } // 插入后调整红黑树 private void fixAfterInsert(RBTreeNode cur) { while (cur.parent ! null cur.parent.color Color.RED) { RBTreeNode parent cur.parent; RBTreeNode grandFather parent.parent; // 父节点是祖父左孩子 if (parent grandFather.left) { RBTreeNode uncle grandFather.right; // 情况1叔叔是红色 if (uncle ! null uncle.color Color.RED) { parent.color Color.BLACK; uncle.color Color.BLACK; grandFather.color Color.RED; cur grandFather; } else { // 情况3叔叔是黑色cur是右孩子 if (cur parent.right) { rotateLeft(parent); cur parent; parent cur.parent; } // 情况2叔叔是黑色cur是左孩子 rotateRight(grandFather); parent.color Color.BLACK; grandFather.color Color.RED; break; } } else { // 父节点是祖父右孩子对称逻辑 RBTreeNode uncle grandFather.left; if (uncle ! null uncle.color Color.RED) { parent.color Color.BLACK; uncle.color Color.BLACK; grandFather.color Color.RED; cur grandFather; } else { if (cur parent.left) { rotateRight(parent); cur parent; parent cur.parent; } rotateLeft(grandFather); parent.color Color.BLACK; grandFather.color Color.RED; break; } } } root.color Color.BLACK; // 根节点永远黑色 } // 插入节点 public boolean insert(int val) { if (root null) { root new RBTreeNode(val); root.color Color.BLACK; return true; } RBTreeNode cur root; RBTreeNode parent null; while (cur ! null) { parent cur; if (val cur.val) cur cur.left; else if (val cur.val) cur cur.right; else return false; } RBTreeNode newNode new RBTreeNode(val); if (val parent.val) parent.left newNode; else parent.right newNode; newNode.parent parent; fixAfterInsert(newNode); return true; } // 中序遍历 public void inOrder(RBTreeNode node) { if (node null) return; inOrder(node.left); System.out.print(node.val ); inOrder(node.right); } public RBTreeNode getRoot() { return root; } }四、AVL 树 vs 红黑树到底选哪个表格对比维度AVL 树红黑树平衡标准绝对平衡高度差≤1近似平衡最长路径≤2× 最短旋转次数多插入 / 删除频繁旋转少调整成本低查找效率略优树高更低稍逊但差距极小修改效率低高适用场景静态数据极少增删动态数据频繁增删一句话总结查多用 AVL增删多用红黑树。五、红黑树的实际应用红黑树因为高效的动态操作性能几乎垄断了工程界的有序存储场景JavaTreeMap、TreeSet 底层实现C STLmap/set、multimap/multisetLinux 内核进程调度管理、epoll 事件块管理Nginx定时器管理六、总结二叉搜索树高效但易退化平衡二叉树是解决方案AVL 树绝对平衡查找快、修改慢适合静态数据红黑树近似平衡增删高效是工程首选两者时间复杂度均为O(log₂N)红黑树实用性更强平衡二叉树是数据结构的核心考点也是后端开发、算法面试的高频内容吃透 AVL 树和红黑树能帮你轻松搞定有序存储的核心问题