系列文章目录

数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客

数据结构之LinkedList-CSDN博客

数据结构之栈_栈有什么方法-CSDN博客

数据结构之队列-CSDN博客

数据结构之二叉树-CSDN博客

数据结构之优先级队列-CSDN博客

常见的排序方法-CSDN博客

数据结构之Map和Set-CSDN博客

系列文章目录

前言

一、二叉搜索树

1. 二叉搜索树的性质

2. 二叉搜索树的查询性能

二、AVL树

1. AVL 树的性质

2. AVL树的节点定义

3. AVL树节点的插入

4. AVL树的验证

1. 验证其为二叉搜索树

2. 验证其为平衡树

5. AVL树的性能分析

三、红黑树

1. 红黑树的性质

2. 红黑树的节点定义

3. 红黑树节点的插入

4. 红黑树的验证

四、AVL树和红黑树的比较

前言

本文介绍了两种自平衡二叉搜索树：AVL树和红黑树。AVL树通过保持左右子树高度差不超过1来实现严格平衡，其查询效率为O(logN)，但在插入删除时需要频繁旋转调整。红黑树通过颜色规则（无连续红节点、路径黑节点数相同）实现近似平衡，最长路径不超过最短路径两倍，虽然查询效率略低于AVL树，但插入删除时旋转次数较少，实际应用更广泛。文章详细阐述了两者的性质、节点结构、插入操作（含平衡调整逻辑）及验证方法，并通过性能对比说明AVL树适合读多写少场景，红黑树更适合频繁修改的场景。

一、二叉搜索树

1. 二叉搜索树的性质

二叉搜索树中的左孩子的值都小于根节点的值，右孩子的值都大于根节点的值；

二叉搜索树的中序遍历是一个有序数组；

2. 二叉搜索树的查询性能

如果在二叉搜索树中连续插入的值都比之前插入的值大，那么二叉搜索树会变成一棵右单树，查询效率就会从原来的 O(logN) 退化成 O(N)；

为了保证二叉搜索树的查询效率，就引入了高度平衡的二叉搜索树，即 AVL 树；

二、AVL树

1. AVL 树的性质

AVL树是一棵高度平衡的二叉搜索树，即左右子树的高度差不超过 1；

2. AVL树的节点定义

val 表示节点的值；

bf 表示平衡因子，计算方法为 右树的高度 - 左树的高度；

left 表示左子树；

right 表示右子树；

parent 表示父亲节点；

public class AVLTree {static class TreeNode{public int val;public int bf;public TreeNode left;public TreeNode right;public TreeNode parent;public TreeNode(int val){this.val = val;}}// 二叉搜索树的属性及方法// ......
}

3. AVL树节点的插入

root 表示 AVL 树的根节点；

insert(int val): boolean 在 AVL 树中插入节点；

思路：

1. 如果树为空，那么新插入的节点就是树的根节点；

2. 查找

节点的插入方式和二叉搜索树相同，定义 cur 找要插入节点的位置，parent 指向 cur 的父节点；

如果 cur 的值小于 val，去右子树找，如果 cur 的值大于 val，去左子树找找，如果 cur 的值等于 val，说明节点已经存在，不能进行插入，返回 false 即可；

3. 插入

如果 cur 为空，表示找到了插入位置，如果节点的值小于 parent 的值，插入到 parent 左边，如果节点的值大于 parent 的值，插入到 parent 的右边，再让 cur 重新指向新插入的节点；

4. 修改平衡因子

如果 cur 是 parent 的左子树，说明插入的节点在 parent 左边，左子树的高度增加了，因此 parent 的平衡因子减 1；

如果 cur 是 parent 的右子树，说明插入的节点在 parent 右边，右子树的高度增加了，因此 parent 的平衡因子加 1；

5. 判断平衡因子

如果修改完 parent 的平衡因子等于 0，表示 parent 这棵树已经平衡了，同时 0 不会影响整棵树的平衡，直接返回 true 即可；

如果修改完 parent 的平衡因子等于 1 或者 -1，表示 parent 平衡，但是可能会影响整棵树的平衡，需要继续向上调整平衡因子，因此 cur 指向 parent，parent 重新指向 cur 的父节点，继续向上调整；

6. 树的调整

继续向上调整的过程中，如果修改完 parent 的平衡因子等于 2 或者 -2，表示 parent 这棵树已经不平衡了，此时需要进行旋转操作，来使得树重新达到平衡；

如果 parent 的平衡因子等于 2，并且 cur 的平衡因子等于 1，表示 parent 和 cur 子树的右子树高度高，此时通过左旋 parent 使树重新达到平衡；

    private void rotateLeft(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;// 修改四个指向parent.right = subRL;subR.left = parent;if(subRL != null){subRL.parent = parent;}// 修改 parent 的父节点之前，保存 parent 的父节点TreeNode pParent = parent.parent;parent.parent = subR;if(root == parent){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 的平衡因子等于 -2，并且 cur 的平衡因子等于 -1，表示 parent 和 cur 子树的左子树高度高，此时通过右旋 parent 使树重新达到平衡；

    private void rotateRight(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;// 修改四个指向parent.left = subLR;subL.right = parent;if(subLR != null){subLR.parent = parent;}// 记录父节点的父节点，旋转完成会用到TreeNode pParent = parent.parent;parent.parent = subL;// 修改 subL 的指向if(root == parent){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 的平衡因子等于 2，并且 cur 的平衡因子等于 -1，表示 parent子树的右子树高度高，cur 子树的左子树高度高，此时通过右旋 cur 子树，降低 cur 左树的高度，再左旋 parent 子树，降低 parent 右树的高度，使树重新达到平衡；

    private void rotateRL(TreeNode parent){TreeNode subR = parent.right;TreeNode subRL = subR.left;int bf = subRL.bf;rotateRight(subR);rotateLeft(parent);if(bf == -1){parent.bf = 0;subRL.bf = 0;subR.bf = 1;}else if(bf == 1){parent.bf = -1;subRL.bf = 0;subR.bf = 0;}}

如果 parent 的平衡因子等于 -2，并且 cur 的平衡因子等于 1，表示 parent子树的左子树高度高，cur 子树的右子树高度高，此时通过左旋 cur 子树，降低 cur 右树的高度，再右旋 parent 子树，降低 parent 左树的高度，使树重新达到平衡；

    private void rotateLR(TreeNode parent){TreeNode subL = parent.left;TreeNode subLR = subL.right;int bf = subLR.bf;rotateLeft(subL);rotateRight(parent);if(bf == -1){parent.bf = 1;subL.bf = 0;subLR.bf = 0;}else if(bf == 1){subL.bf = -1;subLR.bf = 0;parent.bf = 0;}}

修改平衡因子需要从下往上依次修改，直到 parent 为空；

代码实现：

    public TreeNode root;public boolean insert(int val){// 1. 插入节点TreeNode node = new TreeNode(val);if(root == null){root = node;return true;}TreeNode parent = null;TreeNode cur = root;while(cur != null){if(cur.val < val){parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur = cur.left;}else{return false;}}// cur == nullif(parent.val < val){parent.right = node;}else{parent.left = node;}node.parent = parent;cur = node;// 2. 平衡因子的修改while(parent != null){if(cur == parent.left){parent.bf--;}else{parent.bf++;}if(parent.bf == 0){return true;}else if(parent.bf == 1 || parent.bf == -1){cur = parent;parent = parent.parent;}else{if(parent.bf == 2){if(cur.bf == 1){// 左单旋rotateLeft(parent);}else{// cur.bf == -1rotateRL(parent);}}else{ // parent.bf == -2if(cur.bf == -1){// 右单旋rotateRight(parent);}else{rotateLR(parent);}}return true;}}return true;}

4. AVL树的验证

1. 验证其为二叉搜索树

利用二叉搜索树的性质：二叉搜索树的中序遍历是一个有序数组；

    // 中序遍历 - 有序表示当前树是二叉搜索树public void inOrder(TreeNode root){if(root == null){return;}inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

2. 验证其为平衡树

如果每一棵子树都是平衡树，则这棵树是平衡树；

    public int getHeight(TreeNode root){if(root == null) return 0;int left = getHeight(root.left);if(left == -1) return -1;int right = getHeight(root.right);if(right == -1) return -1;if(Math.abs(left - right) > 1) return -1;return Math.max(left, right) + 1;}

5. AVL树的性能分析

AVL树是一个高度绝对平衡的二叉搜索树，查询的时间复杂度为O(longN)；

当时AVL树插入或者删除节点的时候就会涉及到大量的旋转，性能比较低；

因此 AVL 树适用于查询数据，并且这些数据不会被经常修改；

三、红黑树

1. 红黑树的性质

1. 每个节点不是红色就是黑色；
2. 根节点是黑色的；
3. 如果一个节点是红色的，则它的两个孩子节点是黑色的（没有两个连续的红色节点）；
4. 对于每个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点；
5. 每个叶子节点都是黑色的（叶子节点指的是空节点）；

2. 红黑树的节点定义

left 表示当前节点的左子树；

right 表示当前节点的右子树；

parent 表示当前节点的父亲节点；

val 表示当前节点的值；

color 表示当前节点的颜色；

RBTreeNode(int val)：表示红黑树节点的构造方法；

注意：红黑树默认插入节点的颜色是红色的；

如果插入节点是黑色的，为了满足红黑树不同路径上具有相同数量黑色节点的性质，那么就需要在所有路径上都插入一个黑色节点，这些节点是没有意义的，因此默认节点是红色；

public class RBTree {static class RBTreeNode{public RBTreeNode left;public RBTreeNode right;public RBTreeNode parent;public int val;public COLOR color;public RBTreeNode(int val){this.val = val;// 节点默认的颜色为红色，因为如果插入黑色节点，会导致不同路径上黑色节点的数量不一样多，// 这样还需要插入额外的黑色节点，才能保持红黑树的性质this.color = COLOR.RED;}}// 红黑树的属性和方法// ......
}

3. 红黑树节点的插入

root 表示红黑树的根节点；

insert(int val): boolean 在红黑树中插入节点；

思路：

1. 如果树为空，那么新插入的节点就是树的根节点，插入后将根节点的颜色置为黑色；

2. 查找

节点的插入方式和二叉搜索树相同，定义 cur 找要插入节点的位置，parent 指向 cur 的父节点；

如果 cur 的值小于 val，去右子树找，如果 cur 的值大于 val，去左子树找找，如果 cur 的值等于 val，说明节点已经存在，不能进行插入，返回 false 即可；

3. 插入

4. 调整颜色

插入一个节点，如果此时插入节点的父亲节点也是红色的，那么就不能满足红黑树不能有两个连续红色节点的性质，因此为了解决这个问题，就需要对红黑树的颜色进行向上调整；

使用 grandFather 指向 parent 节点的父亲节点，uncle 指向 grandFather 的另外一个子节点；

如果 parent 是 grandFather 的左子树，分为以下三种情况处理：

情况 1：parent 为红色，uncle 指向 grandFather 的右子树，且颜色为红色

parent 和 uncle 调整为黑色，grandFather 调整为红色，如下所示：

调整完成后 cur 指向 grandFather，parent 指向 cur 的父亲节点；

情况 2：parent 为红色，uncle 为黑色，grandFather 为黑色，cur 为 parent 的左子树

先右旋 grandFather，完成后 parent 颜色置为黑色，grandFather 颜色置为红色，如下图：

情况 3：parent 为红色，uncle 为黑色，grandFather 为黑色，cur 为 parent 的右子树
先左旋 parent，再交换 parent 和 cur 指向的位置，得到的情况和情况 2 是相同的，之后再按照情况的处理方式进行处理即可，如下图：

同理，如果 parent 是 grandFather 的左子树，也分为以下三种情况处理：

情况 1：parent 为红色，uncle 指向 grandFather 的左子树，且颜色为红色

parent 和 uncle 调整为黑色，grandFather 调整为红色，如下所示：

调整完成后 cur 指向 grandFather，parent 指向 cur 的父亲节点；

情况 2：parent 为红色，uncle 为黑色，grandFather 为黑色，cur 为 parent 的右子树

先左旋 grandFather，完成后 parent 颜色置为黑色，grandFather 颜色置为红色，如下图：

情况 3：parent 为红色，uncle 为黑色，grandFather 为黑色，cur 为 parent 的左子树
先右旋 parent，再交换 parent 和 cur 指向的位置，得到的情况和情况 2 是相同的，之后再按照情况的处理方式进行处理即可，如下图：

5. 处理根节点

向上调整颜色完成后，根节点有可能会被调整为红色，这是要重新把根节点的颜色调整为黑色，返回 true；

    public RBTreeNode root;public boolean  insert(int val){RBTreeNode node = new RBTreeNode(val);if(this.root == null){this.root = node;this.root.color = COLOR.BLACK;return true;}RBTreeNode cur = root;RBTreeNode parent = null;while(cur != null){if(cur.val < val){parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur = cur.left;}else{return false;}}// cur == null，找到了应该插入的位置if(parent.val < val){parent.right = node;}else{parent.left = node;}node.parent = parent;cur = node;// 修改颜色while(parent != null && parent.color == COLOR.RED){RBTreeNode grandFather = parent.parent;if(grandFather.left == parent){RBTreeNode uncle = grandFather.right;// 情况 1if(uncle != null && uncle.color == COLOR.RED){parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;cur = grandFather;parent = cur.parent;}else{// parent.color == COLOR.BLANK || uncle.color == COLOR.BLANK// 情况 3：if(parent.right == cur){// 左旋rotateLeft(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}// 情况 2 grandFather.color = COLOR.BLANK uncle.color == COLOR.BLANKrotateRight(grandFather);parent.color = COLOR.BLACK;grandFather.color = COLOR.RED;}}else{// grandFather.right = parentRBTreeNode uncle = grandFather.left;// 情况 1：if(uncle != null && uncle.color == COLOR.RED){parent.color = COLOR.BLACK;uncle.color = COLOR.BLACK;grandFather.color = COLOR.RED;cur = grandFather;parent = cur.parent;}else{// parent.color == COLOR.BLANK || uncle.color == COLOR.BLANK// 情况 3：if(parent.left == cur){rotateRight(parent);RBTreeNode tmp = parent;parent = cur;cur = tmp;}// 情况 2：rotateLeft(grandFather);grandFather.color = COLOR.RED;parent.color = COLOR.BLACK;}}}this.root.color = COLOR.BLACK;return true;}

4. 红黑树的验证

验证红黑树分两步：

第一步，验证其为二叉搜索树，采用中序遍历的方式

    // 第一步：验证是否为二叉搜索树public void inOrder(RBTreeNode root){if(root == null) return;inOrder(root.left);System.out.print(root.val + " ");inOrder(root.right);}

第二步，验证红黑树的性质：

根节点为黑色；
没有连续的红色节点；
每条路径上的黑色节点的数量是相同的；

    public boolean isRBTree(RBTreeNode root, int pathBlackNum, int blackNum){if(root == null) {return true;}// 验证红黑树的性质，分为三个性质进行验证// 第一步：验证根节点是否为黑色if(root.color == COLOR.RED){System.out.println("根节点为红色！");return false;}boolean flag = false;// 第二步：验证是否存在连续的两个红色的节点flag = checkRedNode(root);if(!flag) return false;// 第三步：验证是否每条路径上的黑色节点数量都相同flag = checkBlackNodeNum(root, pathBlackNum, blackNum);if(!flag) return false;return true;}private boolean checkRedNode(RBTreeNode root){if(root == null){return true;}// 遍历二叉树，如果遇到红色的节点，看一下它的父节点是否为红色即可if(root.color == COLOR.RED){RBTreeNode parent = root.parent;if(parent.color == COLOR.RED){System.out.println("连续两个红色的节点！");return false;}}return checkRedNode(root.left) && checkRedNode(root.right);}private boolean checkBlackNodeNum(RBTreeNode root, int pathBlackNum, int blackNum) {if(root == null){if(pathBlackNum == blackNum){return true;}System.out.println("路径上的黑色节点数量不相同！");return false;}if(root.color == COLOR.BLACK){pathBlackNum++;}return checkBlackNodeNum(root.left, pathBlackNum, blackNum) &&checkBlackNodeNum(root.right, pathBlackNum, blackNum);}