树的遍历树的回顾树的定义回想一下，一棵树由以下部分组成： 一组节点（或顶点）。 连接这些节点的一组边。 约束：任意两个节点之间只有一条路径。 树有什么用？到目前为止，我们已经了解了搜索树、尝试、堆、不相交集等。这些在我们创建高效算法的过程中非常有用：加快搜索项、允许添加前缀、检查连通性等。 但事实是它们比我们意识到的更加普遍。考虑一个组织结构图。在这里，总统是“根”。 “VP”是根的子代，依此类推。 另一个树结构是桌面上的 61b/ 目录（它就在您的桌面上，不是吗？）。正如我们所看到的，当您遍历到子文件夹时，它会转到后续子文件夹，依此类推。这简直就像树一样！ Tree Iteration Traversal回想一下我们如何学会遍历列表的？有一种遍历列表的方式感觉很自然。就是从开头开始…然后继续往下走。 或者也许我们做了一些有点奇怪的事情，比如遍历列表的反向。回想一下，我们还在讨论中编写了迭代器，以跳过没有在 Office Hours 排队中写描述的学生。 现在如何遍历一棵树呢？什么是正确的“顺序”？ 在回答这个问题之前，我们不能使用迭代这个词。相反，我们将称之为“遍历树” ...

项目2：Gitlet | CS 61B 2021 年春季 — Project 2: Gitlet | CS 61B Spring 2021 (datastructur.es)要求介绍 翻译项目 2: Gitlet关于此规范的说明此规范相当长。前半部分详细描述了您将支持的每个命令，另一半是测试详细信息和一些建议。为了帮助您理解，我们准备了许多高质量的视频，描述了规范的各个部分，并提供建议。所有视频都链接在本规范的相关位置，但我们也将在此列出它们以方便您查看。请注意：这些视频中的一些是在 2020 年春季创建的，当时 Gitlet 是项目 3，Capers 是 Lab 12，并且一些视频简要提及了 Hilfinger 教授的 CS 61B 设置（包括名为 shared 的远程，名为 repo 的存储库等）。请忽略这些内容，因为它们对本学期的您没有任何有用的信息。任务的实际内容没有改变。 Git 介绍 - 第 1 部分 Git 介绍 - 第 2 部分 直播讲座 12 Gitlet 介绍播放列表 第 1 部分 第 2 部分 第 3 部分 第 4 部分 Itai 使用的幻灯片 合并概述和示 ...

代码介绍在Lab8 起始代码在skeleton-sp21/lab8 at master · Berkeley-CS61B/skeleton-sp21 (github.com)仓库中 收获点本次Lab主要介绍了工厂化代码的思想 启动文件的继承结构如下： 1234567Map61B.java└── MyHashMap.java ├── MyHashMapALBuckets.java ├── MyHashMapHSBuckets.java ├── MyHashMapLLBuckets.java ├── MyHashMapPQBuckets.java └── MyHashMapTSBuckets.java 在这个哈希表中，有一个工厂方法 createBucket() 和 createTable(int tableSize)。 createBucket() 方法用于创建一个存储 Node 的桶。在下面的实现中，使用 LinkedList 作为桶的数据结构，因此这个工厂方法返回了一个 LinkedList<Node>。你可以通过重写 ...

为什么要使用PQ？我们学到的最后一个 ADT 是二叉搜索树，它使我们能够高效搜索，只需要 logN 时间。这是因为我们可以在搜索的每一步中剔除一半的元素。如果我们更关心快速找到最小或最大元素而不是快速搜索怎么办？ 同时，二叉树中，我们不允许存在两个具有相同的值的情况重新，因此就有了PQ。 优先级队列接口要理解这个抽象数据类型，请考虑一袋物品。您可以向这个袋子中添加物品，也可以从中移除物品等等。唯一的限制是您只能与这个袋子中的最小的物品进行交互。 123456789101112/** (Min) Priority Queue: Allowing tracking and removal of * the smallest item in a priority queue. */public interface MinPQ<Item> { /** Adds the item to the priority queue. */ public void add(Item x); /** Returns the smallest item in the ...

本文由GPT翻译，原文链接为: 原文 数学天花板：你的认知瓶颈在哪里？本·奥林 思考 2015年4月8日 4分钟 某天下午，我的系主任在教职工休息室里碰到了我，提出了一个发人深思的问题。 （他后来承认，他只是好奇是否能够在这个博客上玩傀儡。答案是一个响亮的“是的”：我像一个傀儡一样跳舞。） 那么，我们有天花板吗？ 传统的正统说：“绝对有。”有高智商和低智商。有“数学人”和“非数学人”。有些孩子就是“懂得了”；而其他人则不是。 试着问问成年人有关他们的数学教育：他们把它看作是某种NCAA锦标赛。每个人都会被淘汰，问题只是你能在游戏中坚持多久。“我处理不了代数”意味着第一轮的淘汰。“我在多元微积分停下了”意味着“嘿，我没赢，但我为进入最后四强而自豪。” 但是教师们中间有一个新的正统观念，那就是“绝对没有”。 你得欣赏这种乐观主义，这种大众主义。（看看你椅子下面——每个人都得到了一本范畴论教材！）但我认为你也得像我的朋友Karen一样怀疑。 Karen，我们有天花板吗？ Karen很努力。Karen会问问题。Karen相信自己。但Karen仍然觉得某些数学超出了她的能 ...

目前的问题到目前为止，我们已经了解了一些数据结构，以便有效地搜索数据结构中是否存在项目。我们研究了二叉搜索树，然后使用 2-3 棵树使它们平衡。 然而，这些结构存在一些限制（是的，甚至是 2-3 棵树） 他们要求项目具有可比性。您如何决定新项目在 BST 中的位置？你必须回答“你比根小还是大”的问题？对于某些对象来说，这个问题可能没有意义。 它们给出的复杂度为 Θ(logN) 。这个好吗？绝对地。但也许我们可以做得更好。 第一次尝试： DataIndexedIntegerSet目前，我们只尝试改进上面的问题#2（将复杂性从 Θ(logN) 提高到 Θ(1) 。我们不会担心问题#1（可比性）事实上，我们只会考虑存储和搜索 int 。 这里有一个想法：让我们创建一个类型为 boolean 且大小为 20 亿的 ArrayList。让一切默认为假。 add(int x) 方法只是将 ArrayList 中的 x 位置设置为 true。这需要 Θ(1)Θ(1) 时间。 contains(int x) 方法只是返回 ArrayList 中的 x 位置是 true 还是 false 。这 ...

Reading: 11. 平衡树 ·拥抱61B — 11. Balanced Trees · Hug61B (gitbooks.io) 当我们随机插入 BST 时，平均深度和高度预计为Θ(*logN*) . 但是，我们并不总是能够以随机顺序插入 BST。如果我们的数据是实时的呢？然后，我们将被迫按照数据到达我们的顺序进行插入。 下面我们将了解一棵始终保持平衡的树！ B-trees / 2-3 trees / 2-3-4 treescs61b 2019 lec17 ds3 2-3 trees, 2-3-4 trees - Google 幻灯片 BST 的问题在于我们总是插入叶节点。这就是导致高度增加的原因。 当我们开始插入节点时，我们可能会破坏平衡结构。所以，让我们想出一种方法，在添加新节点时保持树的平衡！ 疯狂的想法：我们永远不要添加叶子节点！当我们插入时，让我们只添加到当前的叶节点。这样，高度永远不会增加。 但是，您能看到这种插入方案的潜在问题吗？如果我们搜索 19，那么我们将向下遍历到包含它的节点，我们仍然必须像查看数组一样查看该节点才能到达 19 元素。这 ...

Lab 7: BSTMap | CS 61B Spring 2021 (datastructur.es) 创建一个 BSTMap 类，它使用 BST（二叉搜索树）作为其核心数据结构来实现 Map61B 接口。您必须在名为 BSTMap.java 的文件中执行此操作。您的实现需要实现 Map61B 中给出的所有方法，但 remove 、 iterator 和 keySet 除外。对于这些方法，您应该抛出一个 UnsupportedOperationException 在创建 BSTMap 类并实现 Map61B 的所有方法之前，您的代码不会编译。您可以一次实现一个方法，方法是编写所有必需方法的方法签名，但为实现抛出 UnsupportedOperationExceptions ，直到您真正开始编写它们。 您的 BSTMap 还应该添加一个附加方法 printInOrder() （Map61B 接口中未给出），该方法按 Key 递增的顺序打印出 BSTMap。我们不会测试此方法的结果，但您会发现这对测试您的实现很有帮助！ 资源 Lecture 16 slides. 讲座 16 幻灯片。 ...