• 暂时停更一段时间!
  • 近期网站将陆续进行前端页面改造!
  • 招募网站编辑,联系站长!

标签:数据结构笔记总结

数据结构笔记总结(12.1)红黑树与2-3树

《算法导论》中的红黑树1、每个节点或者是红色的,或者是黑色的2、根节点是黑色的3、每一个叶子节点(最后的空节点)是黑色的4、如果一个节点是红色的,那么他的孩子节点都是黑色的5、从任意一个节点到叶子节点,经过的黑色节点是一样的2-3 树满足二分搜索树的基本性质节点可以存放一个元素或者两个元素每个节点有 2 个或者 3 个孩子,2-3 树是一……

数据结构笔记总结(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……

数据结构笔记总结(11.6)LR 和 RL

LL 和 RR将前两节的情况重新命名新插入的节点 z 在 y 左孩子的右侧(LR)首先对 x 进行左旋转,转为了 LL 的情况。新插入的节点 z 在 y 右孩子的左侧(RL)首先对 x 进行右旋转,转化成了 RR 的情况。代码实现// 平衡维护//LLif (balanceFactor > 1 && ……

数据结构笔记总结(11.5)左旋转和右旋转的实现

右旋转具体编码实现// 对节点 y 进行向右旋转操作,返回旋转后新的根节点 x// y x// / \ / \// x T4 向右旋转 (y) z y//……

数据结构笔记总结(11.4)旋转操作的基本原理

AVL 树在什么时候维护平衡在二分搜素树中,如果要插入一个节点的话,需要从根节点开始一路下来,最终寻找到正确的插入位置,正确的插入位置都是叶子节点的位置。由于我们新添加一个节点才能导致整个二叉树不再平衡,相应的不平衡节点只有可能发生在从我们插入的位置开始,向父亲去找,因为是我们插入这个几点才破坏平衡性,那么它将反应在相应的父亲节点或祖先节点。所以维护……

数据结构笔记总结(11.3)检查二分搜索树性质和平衡性

检查二分搜索树性质和平衡性这一小节我们再来做一个辅助工作,设置两个函数来判断当前的这个树是不是二分搜索树,同时是不是平衡二叉树。对于 AVL 树来说,它是对二分搜索树的一个改进,改进的是二分搜索树有可能退化成链表这种情况,因此引入了平衡因子的概念。AVL 树要保证每个节点中左右子树的差不超过 1,但是要注意 AVL 树同时也是一个二分搜索树,所以也要满……

数据结构笔记总结(11.2)计算节点的高度和平衡因子

计算节点的高度和平衡因子在上一小节中,为了保持二分搜索树的平衡,对每一个节点应该记录一个高度值,通过高度值可以得到平衡因子这样一个值,根据平衡因子可以进行一些后续的操作来保持平衡。改进原来的二分搜索树代码我们先改进原来的 BST 二分搜索树的代码,让它可以记录节点的高度值并计算平衡因子。import java.util.ArrayList;……

数据结构笔记总结(11.1)平衡二叉树和AVL

回忆二分搜素树的问题二分搜素树存在一个严重的问题,就是如果数据是顺序添加进二分搜素树的,如下图所示按照 1,2,3,4,5,6,的顺序创建二叉树的话,整个二分搜素树将退化为一个链表,它会大大降低二分搜素树的效率。解决办法:在现有的二分搜素树基础上添加一定的机制使得二分搜素树能够维持平衡二叉树的性质AVL 树这个名称是根据两个发明人的首字母缩写来命名……

《数据结构笔记总结》导航页

导航目录第一章:数组     数据结构笔记总结(1.1)使用 Java 中的数组    数据结构笔记总结(1.2)二次封装属于我们自己的数组    数据结构笔记总结(1.3)向数组中添加元素  &n……

数据结构笔记总结(10.7)更多和并查集相关的话题

改进第六版的并查集借助递归实现查询一个节点的时候,将这个节点以及这个节点之前的所有节点全都直接指向根节点。// 我们的第六版 Union-Findpublic class UnionFind6 implements UF { // rank[i]表示以 i 为根的集合所表示的树的层数 // 在后续的代码中, 我们并不会维护……

数据结构笔记总结(10.6)路径压缩

路径压缩这一小节我们再来看一下并查集非常重要的一种优化方式–路径压缩(Path Compression)。用着三种方式表示我们这个五个节点是互相连接的,它们其实是等效的,具体查询过程中,无论是调用 find,还是 isConnected,在这三种树中去查询五个节点任意两个节点都是相连接的。但是由于这三种树深度不同,所以其实效率是不同的,对……

数据结构笔记总结(10.5)基于rank的优化

基于 rank 的优化上一小节对我们实现的并查集进行了基于 size 的优化,基于并查集中的一颗树的大小进行的优化,优化的目的在于合并两棵树的时候得到的新树整体高度尽量不要每次都进行深度的增加。对于我们这个思想,其实更直接的一种方式通常在并查集称为基于 rank 的优化,这里的 rank 其实就是指树的高度或深度,为什么不叫做 height 或者 dep……

数据结构笔记总结(10.4)基于size的优化

并查集的优化前两节我们实现了两种并查集,第一版的并查集其实就是使用数组来模拟每个数据所属的集合是谁,第二版虽然依然使用数组来进行数据关系的存储,但整体思路上和第一版的并查集是截然不同的,让数据形成了一种比较奇怪的树结构,或者说是森林结构。改进并查集这里我们先回忆一下第二版的 Quick Union 的过程,首先执行 union(0,1),结果如下下……

数据结构笔记总结(10.3)Quick Union

Quick Union上一节我们实现了并查集的一种思路,使用数组进行模拟得到一种结果,叫做 Quick Find,对于查找这种操作是非常快的。标准情况下并查集的实现是通过 Quick Union 这种实现思路。实现思路将每一个元素看做是一个节点,节点之间相连接形成一棵树的结构,不过这棵树结构和之前所学的树结构都是不同的,并查集中的树结构是孩子指向父亲……

数据结构笔记总结(10.2)Quick Find

并查集的基本数据表示在并查集内部我们可以直接给每个数据做一个编号,这里 0 到 9 就表示 10 个不同的数据当然这是一种抽象的表示,10 个编号可能是 10 个人或 10 辆车,但在并查集内部我们只存 0 到 9 这 10 个编号,它表示 10 个具体的元素。对于每一个元素并查集存储的是一个我们可以称之为叫做它所属于的集合的 ID,比如编号为 0……

数据结构笔记总结(10.1)什么是并查集

并查集(Union Find)我们之前学习的所有树结构都是由父亲指向孩子,但是并查集却是一种由孩子指向父亲的树结构这样一种数据结构,它可以非常高效的来解决连接问题(Connectivity Problem)如上这个图有非常多的点,每两个点之间有的有一个连接,有的没有连接,使用并查集就可以高效的回答这样一个问题:给出图中任意两点,问两点之间是否可以根据一……

数据结构笔记总结(9.7)更多和Trie字典树相关的话题

Trie 的删除操作我们并没有实现 Trie 的删除操作,在大多数情况下比如竞赛面试使用 Trie 的时候基本上都不会涉及删除操作的。但是如果在实际应用中使用 Trie 的话,很多时候是要涉及删除操作的。比如我们做一个通讯录,使用 Trie 创建通讯录的话,我们将通讯录中的每一个人名当做单词插入到 Trie 中,在单词最后一个字母的位置存储相应的通讯录……

数据结构笔记总结(9.6)Trie字典树和字符串映射

Trie 字典树和字符串映射前面实现的 Trie 都是把它当成一个字符串的集合来使用,主要在 Trie 中添加或查询一个单词是否存在。在查询方面上一小节通过一个 LeetCode 问题知道了还可以进行一定的字符串模式匹配,这一小节我们具体来看看当我们把 Trie 当成一个映射来使用的情况是怎样的?677. 键值映射实现一个 MapSum 类里的两个……

数据结构笔记总结(9.5)Trie字典树和简单的模式匹配

211. 添加与搜索单词 – 数据结构设计设计一个支持以下两种操作的数据结构:void addWord(word)bool search(word)search(word) 可以搜索文字或正则表达式字符串,字符串只包含字母 . 或 a-z 。 . 可以表示任何一个字母。示例:addWord(“bad”)add……

数据结构笔记总结(9.4)Trie字典树的前缀查询

Trie 字典树的前缀查询Trie 中文名称叫“字典树”,字典树很好理解,它是一个树结构,存储的是一个个字符串。把它合在一起就像一个字典,同时它又叫前缀树,就是因为我们可以非常容易在 Trie 中搜索某个单词对应的前缀其实这种搜索非常简单,可以想象一下 Trie 的结构,从根节点开始,向下搜索的过程其实都是在搜索单词的前缀。比如我在查找 cat 的……

数据结构笔记总结(9.3)Trie字典树的查询

如何从 Trie 中查询单词// 查询单词 word 是否在 Trie 中public boolean contains(String word){ Node cur = root; for(int i = 0 ; i < word.length() ; i ++){ char c = word.ch……

数据结构笔记总结(9.2)Trie字典树基础

完成 Trie 字典树import java.util.TreeMap;public class Trie { private class Node{ public boolean isWord; public TreeMap<Character, Node> next;……

数据结构笔记总结(9.1)什么是Trie字典树

什么是 Trie这种数据结构和我们之前介绍的所有树结构都不同的一种树,之前介绍的所有树结构,无论是二分搜素树还是堆还是线段树都是二叉树,但是 Trie 是一个多叉树,下面和字典来做一下比较Trie 是怎么做到查询的时间复杂度和条目数无关而只和单词中有多少个字符相关的呢?之前我们在考察字符串、单词这样一个数据的时候,我们会把整个字符串看成一个整体。……

数据结构笔记总结(8.6)线段树中的更新操作

307. 区域和检索 – 数组可修改给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。update(i, val) 函数可以通过将下标为 i 的数值更新为 val,从而对数列进行修改。示例:Given nums = [1, 3, 5]sumRange(0, 2) ->……