网站备案需要多少钱,宜家家居官网网上商城,做视频剪辑接私活的网站,新乡网站系列文章目录
数据结构之ArrayList_arraylist o(1) o(n)-CSDN博客
数据结构之LinkedList-CSDN博客
数据结构之栈_栈有什么方法-CSDN博客
数据结构之队列-CSDN博客
数据结构之二叉树-CSDN博客
数据结构之优先级队列-CSDN博客
常见的排序方法-CSDN博客
数据结构之Map和Se…系列文章目录
数据结构之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 指向 parentparent 重新指向 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. 插入
如果 cur 为空表示找到了插入位置如果节点的值小于 parent 的值插入到 parent 左边如果节点的值大于 parent 的值插入到 parent 的右边再让 cur 重新指向新插入的节点
4. 调整颜色
插入一个节点如果此时插入节点的父亲节点也是红色的那么就不能满足红黑树不能有两个连续红色节点的性质因此为了解决这个问题就需要对红黑树的颜色进行向上调整
使用 grandFather 指向 parent 节点的父亲节点uncle 指向 grandFather 的另外一个子节点
如果 parent 是 grandFather 的左子树分为以下三种情况处理
情况 1parent 为红色uncle 指向 grandFather 的右子树且颜色为红色
parent 和 uncle 调整为黑色grandFather 调整为红色如下所示 调整完成后 cur 指向 grandFatherparent 指向 cur 的父亲节点
情况 2parent 为红色uncle 为黑色grandFather 为黑色cur 为 parent 的左子树
先右旋 grandFather完成后 parent 颜色置为黑色grandFather 颜色置为红色如下图 情况 3parent 为红色uncle 为黑色grandFather 为黑色cur 为 parent 的右子树 先左旋 parent再交换 parent 和 cur 指向的位置得到的情况和情况 2 是相同的之后再按照情况的处理方式进行处理即可如下图 同理如果 parent 是 grandFather 的左子树也分为以下三种情况处理
情况 1parent 为红色uncle 指向 grandFather 的左子树且颜色为红色
parent 和 uncle 调整为黑色grandFather 调整为红色如下所示 调整完成后 cur 指向 grandFatherparent 指向 cur 的父亲节点
情况 2parent 为红色uncle 为黑色grandFather 为黑色cur 为 parent 的右子树
先左旋 grandFather完成后 parent 颜色置为黑色grandFather 颜色置为红色如下图 情况 3parent 为红色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// 情况 3if(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;// 情况 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// 情况 3if(parent.left cur){rotateRight(parent);RBTreeNode tmp parent;parent cur;cur tmp;}// 情况 2rotateLeft(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);}
四、AVL树和红黑树的比较 AVL树和红黑树都是二叉搜索树也都是二叉平衡树
AVL树追求绝对的高度平衡即左右子树的高度差不超过 1
红黑树不追求绝对平衡保证每条路径上的黑色节点的数量相同即可且没有连续的红色节点即最长路径上的长度是最短路径长度的二倍
AVL树在插入和删除节点的时候需要大量的旋转不适合进行频繁的插入和删除
红黑树在插入和删除节点的时候减少了旋转的次数因此在实际应用中更多
