Geekerstar 《数据结构笔记总结》导航页
导航目录 第一章：数组 数据结构笔记总结（1.1）使用Java中的数组 数据结构笔记总结（1.2）二次封装属于我们自己的数组 数据结构笔记总结（1.3）向数组中添加元素 数据结构笔记总结（1.4）数组中查询元素和 …
赞助用户专享优质资源内容持续上新
数据结构笔记总结（12.1）红黑树与2-3树
《算法导论》中的红黑树 1、每个节点或者是红色的，或者是黑色的 2、根节点是黑色的 3、每一个叶子节点（最后的空节点）是黑色的 4、如果一个节点是红色的，那么他的孩子节点都是黑色的 5、从任意一个节点 …
数据结构笔记总结（11.7）从AVL树中删除元素
private Node remove(Node node, K key){ if( node == null ) return null; Node retNode; if( key.compareTo(node.key) < 0 ){ node.left = remove(node.left , key); // return node; retNode = node; } …
数据结构笔记总结（11.6）LR 和 RL
LL和RR 将前两节的情况重新命名 新插入的节点z在y左孩子的右侧（LR） 首先对x进行左旋转，转为了LL的情况。 新插入的节点z在y右孩子的左侧（RL） 首先对x进行右旋转，转化成了RR的情况。 代码实现 // 平衡 …
数据结构笔记总结（11.5）左旋转和右旋转的实现
右旋转具体编码实现 // 对节点y进行向右旋转操作，返回旋转后新的根节点x // y x // / \ / \ // x T4 向右旋转 (y) z y // / \ - - - - - - - -> / \ / \ // z T3 T1 T2 T3 T4 // / \ // T1 T2 private Nod …
数据结构笔记总结（11.4）旋转操作的基本原理
AVL树在什么时候维护平衡 在二分搜素树中，如果要插入一个节点的话，需要从根节点开始一路下来，最终寻找到正确的插入位置，正确的插入位置都是叶子节点的位置。 由于我们新添加一个节点才能导致整个二叉树 …
数据结构笔记总结（11.3）检查二分搜索树性质和平衡性
检查二分搜索树性质和平衡性 这一小节我们再来做一个辅助工作，设置两个函数来判断当前的这个树是不是二分搜索树，同时是不是平衡二叉树。 对于AVL树来说，它是对二分搜索树的一个改进，改进的是二分搜索树 …
数据结构笔记总结（11.2）计算节点的高度和平衡因子
计算节点的高度和平衡因子 在上一小节中，为了保持二分搜索树的平衡，对每一个节点应该记录一个高度值，通过高度值可以得到平衡因子这样一个值，根据平衡因子可以进行一些后续的操作来保持平衡。 改进原来 …
数据结构笔记总结（11.1）平衡二叉树和AVL
回忆二分搜素树的问题 二分搜素树存在一个严重的问题，就是如果数据是顺序添加进二分搜素树的，如下图所示按照1,2,3,4,5,6,的顺序创建二叉树的话，整个二分搜素树将退化为一个链表，它会大大降低二分搜素树 …
数据结构笔记总结（10.7）更多和并查集相关的话题
改进第六版的并查集 借助递归实现查询一个节点的时候，将这个节点以及这个节点之前的所有节点全都直接指向根节点。 // 我们的第六版Union-Find public class UnionFind6 implements UF { // rank[i]表示以i …
数据结构笔记总结（10.6）路径压缩
路径压缩 这一小节我们再来看一下并查集非常重要的一种优化方式–路径压缩（Path Compression）。 用着三种方式表示我们这个五个节点是互相连接的，它们其实是等效的，具体查询过程中，无论是调用find …
数据结构笔记总结（10.5）基于rank的优化
基于rank的优化 上一小节对我们实现的并查集进行了基于size的优化，基于并查集中的一颗树的大小进行的优化，优化的目的在于合并两棵树的时候得到的新树整体高度尽量不要每次都进行深度的增加。 对于我们这 …
