目前的问题到目前为止，我们已经了解了一些数据结构，以便有效地搜索数据结构中是否存在项目。我们研究了二叉搜索树，然后使用 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 幻灯片。 ...

Slides:cs61b 2020 lec16 ds2 adts, sets, maps, binary search trees - Google 幻灯片 Reading:10.2 Trees · Hug61B (gitbooks.io) ADTs 抽象数据类型（ADT）仅通过其操作进行定义，而不是通过其实现。 这意味着ADT定义了一组操作或行为，而不涉及具体的实现细节。 例如，在proj1a中，我们开发了一个ArrayDeque和一个LinkedListDeque，它们具有相同的方法，但这些方法的编写方式非常不同。在这种情况下，我们说ArrayDeque和LinkedListDeque是Deque ADT的实现。从这个描述中，我们可以看出ADT和接口在某种程度上是相关的。 ADT强调的是数据和操作的抽象描述，而接口强调的是行为和操作的规范定义。 在概念上，Deque是一个接口，ArrayDeque和LinkedListDeque是其实现。在代码中，为了表达这种关系，我们让ArrayDeque和LinkedListDeque类从Deque接口继承。 一些常用的ADT包括 ...

slide:cs61b 2020 lec14 ds1 disjoint sets - Google 幻灯片 Reading:9.1 Introduction · Hug61B (gitbooks.io) code:Case Study: Union-Find (princeton.edu) Disjoint Sets简介如果两个集合没有共同元素，则称它们为不相交集合。一个不相交集合（或者称为并查集）数据结构用于追踪固定数量的元素，这些元素被划分为多个不相交集合。该数据结构具有两个操作： connect(x, y): 连接 x 和 y。也称为 union。 isConnected(x, y): 如果 x 和 y 连接（即属于同一集合），则返回true。 不相交集合数据结构有一定数量的元素，每个元素最初都位于自己的子集中。通过对某些元素 x 和 y 调用 connect(x, y)，我们可以将子集合并在一起。 例如，假设我们有四个元素，我们将它们称为 A、B、C、D。初始时，每个元素都在自己的集合中： 调用 connect(A, B) 后： 请注意，子集 A 和 B 被合并。让我们 ...

高效编程效率有两种形式： 1.） 编程成本。 开发您的程序需要多长时间？ 读取、修改和维护代码的难易程度如何？ 2.） 执行成本（从下周开始）。 您的程序需要多少时间才能执行？ 您的程序需要多少内存？ 61B 中讨论了一些有用的 Java 特性： 包（Packages） 优点：组织，使事物成为包私有。 缺点：过于具体。 静态类型检查（Static type checking）。 优点：早期检查错误，更像是一篇故事。 缺点：不够灵活，（强制转换等） 继承（Inheritance） 优点：代码重用。 缺点： “Is a”，，调试路径变得烦人，不能实例化，要实现接口的每个方法。 封装首先，我们将定义一些术语： 模块：一组方法，作为整体一起执行某个任务或一组相关任务。 封装的：如果模块的实现完全隐藏，只能通过文档化的接口访问，则称其为封装的。 API（应用程序编程接口）ADT（抽象数据结构）的API是构造函数和方法列表以及每个方法的简短描述。 API由语法和语义规范组成。 编译器验证是否符合语法。 也就是说，API中指定的一切都存在。 测试有助于验证语 ...

6.1 Lists, Sets, and ArraySet · Hug61B (gitbooks.io) 在本节中，我们将学习如何使用 Java 的内置 List 和 Set 数据结构，以及构建我们自己的 ArraySet Java中的Lists我们从头开始构建了一个列表，但 Java 提供了一个内置 List 接口和几个实现，例如 ArrayList .请记住，由于 List 是一个接口，我们无法对其进行设置！我们必须确定它的一个实现。 为了访问它，我们可以使用类、接口的全名（“规范名称”）： 1java.util.List<Integer> L = new java.util.ArrayList<>(); 但是，这有点冗长。以类似于我们导入的方式，我们可以导入 JUnit java 库： 1234567891011import java.util.List;import java.util.ArrayList;public class Example { public static void main(String[] args)
...

幻灯片:cs61b 2021 lec10 inheritance3 - Google 幻灯片 Reading:4.3 Subtype Polymorphism vs. HOFs · Hug61B (gitbooks.io) 子类多态性多态性的核心是“多种形式”。在 Java 中，多态性是指对象可以具有多种形式或类型。在面向对象编程中，多态性涉及如何将一个对象视为其自身类的实例、其超类的实例、其超类的超类的实例等。 考虑一个静态类型为deque的变量deque。调用dequeue .addFirst() 将在执行时确定，这取决于调用 addFirst 时deque的运行时类型或动态类型。正如我们在上一章中看到的，Java使用动态方法选择来选择调用哪个方法。 运行时类型（Runtime Type）： 运行时类型指的是在程序执行过程中，某个变量或对象的实际类型。这是由程序在运行时动态决定的。在一些面向对象的语言中，对象可能被声明为某个类型，但在运行时可能会被赋予该类型的子类型。因此，运行时类型是程序实际处理的对象类型，而不仅仅是在代码中声明的类型。如基类。 动态类型（Dynamic Ty ...