Java据结构深度解析：AVL 树与红黑树-洪萨配资

AVL树

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果能保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树

它的左右子树都是AVL树
左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

如果一棵二叉搜索树是高度平衡的，它就是AVL树。如果它有n个结点，其高度可保持在O（log2N）

搜索时间复杂度O（log2N）

AVL树节点的定义

static class TreeNode{ public TreeNode left; public TreeNode right; public int value; public TreeNode parent; public int bf;//平衡因子 public TreeNode(int value){ this.value=value; } }

比起二次搜索树多了一个平衡因子，当前节点的平衡因子=右子树高度-左子树的高度。但是，不是每棵树，都必须有平衡因子，这只是其中的一种实现方式。

AVL树的插入

1.按照二叉搜索树的方式插入新节点、

这里我们按照上篇文章二叉搜索树的方式进行插入

TreeNode node=new TreeNode(value); if(root==null){ root=node; return true; } TreeNode parent=null; TreeNode cur=root; while(cur!=null){ if(cur.value<value){ parent=cur; cur=cur.right; } else if(cur.value==value){ return false; } else{ parent=cur; cur=cur.left; } } //cur==null if(parent.value<value){ parent.right=node; } else{ parent.left=node; } node.parent=parent; cur=node;

2.调整节点的平衡因子

首先是判断当前cur节点是parent的左孩子或者右孩子

决定平衡因是右孩子++左孩子--

//先看cur是parent的左还是右 决定平衡因子是++还是-- if(cur==parent.right){ //如果是右树 右树平衡因子++ parent.bf++; }else { //左树平衡因子-- parent.bf--; }

然后我们再来判断parent节点的平衡因子等于几应该是有三种情况

parent.bf=0，此时整科树已经平衡 parent.bf=1或parent.bf=-1此时继续向上调整

除此之外parent.bf=2 cur.bf=1此时右树高度高于左树，需要进行左旋

private void roteleft(TreeNode parent){ TreeNode subR=parent.right; TreeNode subRL=subR.left; parent.right=subRL; subR.left=parent; if(subRL!=null){ subRL.parent=parent; } TreeNode pParent=parent.parent; parent.parent=subR; if(parent==root){ root=subR; root.parent=null; } else { if(pParent.left==parent){ pParent.left=subR; }else{ pParent.right=subR; } subR.parent=pParent; } subR.bf=0; parent.bf=0; }

parent.bf=-2 cur.bf=-1此时左树高度高于右树，需要进行右旋

private void rotateright(TreeNode parent){ TreeNode subl=parent.left; TreeNode sublR=subl.right; parent.left=sublR; subl.right=parent; //有可能sublr为空 没有sublR if(sublR!=null){ sublR.parent=parent; } TreeNode pParent=parent.parent; parent.parent=subl; //检查 当前parent是不是根节点 if(parent==root){ root=subl; root.parent=null; } else { //不是根节点 if(pParent.left==parent){ pParent.left=subl; } else{ pParent.right=subl; } subl.parent=pParent; } subl.bf=0; parent.bf=0; }

parent.bf=-2 cur.bf=-1

if(parent.bf==0){ //已经平衡了 break; } else if(parent.bf==1||parent.bf==-1){ //继续向上判断 cur=parent; parent=cur.parent; }else{ if(parent.bf==2){ //右树高度高 if(cur.bf==1){ } else{ //parent.bf==-1 } } else { //parent.bf==-2左树高度高 降低左树高度 if(cur.bf==1){ //右旋 rotateright(parent); } else{ //parent.bf==-1 } } //上诉代码走完，已经平衡了 break; }

AVL树的验证

1.验证其为二叉搜索树
如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
2.验证其为平衡树
每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
节点的平衡因子是否计算正确

private int height(TreeNode root){ if(root==null){ return 0; } int lefth=height(root.left); int righth=height(root.right); return lefth>righth?lefth+1:righth+1; } public boolean isbalance(TreeNode root){ if(root==null){ return true; } int left=height(root.left); int right=height(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× 最短）
旋转次数	多（插入 / 删除频繁旋转）	少（调整成本低）
查找效率	略优（树高更低）	稍逊，但差距极小
修改效率	低	高
适用场景	静态数据（极少增删）	动态数据（频繁增删）