小奏

AVL 树 概述 历史 AVL 树是一种自平衡二叉搜索树，由托尔·哈斯特罗姆在 1960 年提出并在 1962 年发表。它的名字来源于发明者的名字：Adelson-Velsky 和 Landis，他们是苏联数学家，于 1962 年发表了一篇论文，详细介绍了 AVL 树的概念和性质。 在二叉搜索树中，如果插入的元素按照特定的顺序排列，可能会导致树变得非常不平衡，从而降低搜索、插入和删除的效率。为了解决这个问题，AVL 树通过在每个节点中维护一个平衡因子来确保树的平衡。平衡因子是左子树的高度减去右子树的高度。如果平衡因子的绝对值大于等于 2，则通过旋转操作来重新平衡树。 AVL 树是用于存储有序数据的一种重要数据结构，它是二叉搜索树的一种改进和扩展。它不仅能够提高搜索、插入和删除操作的效率，而且还能够确保树的深度始终保持在 O(log n) 的水平。随着计算机技术的不断发展，AVL 树已经成为了许多高效算法和系统中必不可少的一种基础数据结构。 前面介绍过，如果一棵二叉搜索树长的不平衡，那么查询的效率会受到影响，如下图 通过旋转可以让树重新变得平衡，并且不会改变二叉搜索树的性质（即左边 ...

历史 二叉搜索树最早是由Bernoulli兄弟在18世纪中提出的，但是真正推广和应用该数据结构的是1960年代的D.L. Gries。他的著作《The Science of Programming》中详细介绍了二叉搜索树的实现和应用。 在计算机科学的发展中，二叉搜索树成为了一种非常基础的数据结构，被广泛应用在各种领域，包括搜索、排序、数据库索引等。随着计算机算力的提升和对数据结构的深入研究，二叉搜索树也不断被优化和扩展，例如AVL树、红黑树等。 特性 二叉搜索树（也称二叉排序树）是符合下面特征的二叉树： 树节点增加 key 属性，用来比较谁大谁小，key 不可以重复 对于任意一个树节点，它的 key 比左子树的 key 都大，同时也比右子树的 key 都小，例如下图所示 轻易看出要查找 7 （从根开始）自然就可应用二分查找算法，只需三次比较 与 4 比，较之大，向右找 与 6 比，较之大，继续向右找 与 7 比，找到 查找的时间复杂度与树高相关，插入、删除也是如此。 如果这棵树长得还不赖（左右平衡）上图，那么时间复杂度均是 O(log⁡N)O(\log{N})O(log ...

查找概述 查找算法是一种在数据集中寻找特定数据项的方法。通常，数据集是在计算机程序中存储的，例如数组、链表或散列表。在编写程序时，查找算法是非常重要的，它有助于快速找到所需的数据。在本文中，我们将介绍一些基本的查找算法及其特点。 线性查找 线性查找也称为顺序查找，是一种最简单的查找算法。在这种算法中，我们从数据集的开头开始，逐个比较每个数据项，以寻找要查找的数据。如果我们找到了目标数据，查找过程就结束了。如果我们到达数据集的末尾，仍然找不到目标数据，则可以认为它不存在于数据集中。 线性查找的时间复杂度是O(n)，其中n是数据集的大小。因此，它在大型数据集中可能会很慢。然而，在小型数据集中，它仍然是一种非常有用的算法。 二分查找 二分查找也称为折半查找，是一种更快速的查找算法。但前提是，数据集必须已经排序。在二分查找中，我们取数据集的中间值，然后将目标与中间值进行比较。如果目标小于中间值，则在左侧子集中继续查找；如果目标大于中间值，则在右侧子集中继续查找。每次比较都会缩小要搜索的数据集的大小。 二分查找的时间复杂度是O(log n)，其中n是数据集的大小。这种算法在大型数据集中非常有效， ...

二叉树 二叉树是这么一种树状结构：每个节点最多有两个孩子，左孩子和右孩子 重要的二叉树结构 完全二叉树（complete binary tree）是一种二叉树结构，除最后一层以外，每一层都必须填满，填充时要遵从先左后右 平衡二叉树（balance binary tree）是一种二叉树结构，其中每个节点的左右子树高度相差不超过 1 存储 存储方式分为两种 定义树节点与左、右孩子引用（TreeNode） 使用数组，前面讲堆时用过，若以 0 作为树的根，索引可以通过如下方式计算 父 = floor((子 - 1) / 2) 左孩子 = 父 * 2 + 1 右孩子 = 父 * 2 + 2 遍历 遍历也分为两种 广度优先遍历（Breadth-first order）：尽可能先访问距离根最近的节点，也称为层序遍历 深度优先遍历（Depth-first order）：对于二叉树，可以进一步分成三种（要深入到叶子节点） pre-order 前序遍历，对于每一棵子树，先访问该节点，然后是左子树，最后是右子树 in-order 中序遍历，对于每一棵子树，先访问左子树，然后是该节点，最后是 ...

堆 以大顶堆为例，相对于之前的优先级队列，增加了堆化等方法 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136public class MaxHeap { int[] array; int size; public MaxHeap(int capacity) { this.array = new int[capacity]; } /** * 获取堆顶元素 * ...

阻塞队列 之前的队列在很多场景下都不能很好地工作，例如 大部分场景要求分离向队列放入（生产者）、从队列拿出（消费者）两个角色、它们得由不同的线程来担当，而之前的实现根本没有考虑线程安全问题 队列为空，那么在之前的实现里会返回 null，如果就是硬要拿到一个元素呢？只能不断循环尝试 队列为满，那么再之前的实现里会返回 false，如果就是硬要塞入一个元素呢？只能不断循环尝试 因此我们需要解决的问题有 用锁保证线程安全 用条件变量让等待非空线程与等待不满线程进入等待状态，而不是不断循环尝试，让 CPU 空转 有同学对线程安全还没有足够的认识，下面举一个反例，两个线程都要执行入队操作（几乎在同一时刻） 1234567891011121314151617181920public class TestThreadUnsafe { private final String[] array = new String[10]; private int tail = 0; public void offer(String e) { array[ ...

优先级队列 无序数组实现 要点 入队保持顺序 出队前找到优先级最高的出队，相当于一次选择排序 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667public class PriorityQueue1<E extends Priority> implements Queue<E> { Priority[] array; int size; public PriorityQueue1(int capacity) { array = new Priority[capacity]; } @Override // O(1) public boolean offer(E e) { if (isFull()) { return false; ...

双端队列 概述 双端队列、队列、栈对比 定义 特点 队列 一端删除（头）另一端添加（尾） First In First Out 栈 一端删除和添加（顶） Last In First Out 双端队列 两端都可以删除、添加 优先级队列 优先级高者先出队 延时队列 根据延时时间确定优先级 并发非阻塞队列 队列空或满时不阻塞 并发阻塞队列 队列空时删除阻塞、队列满时添加阻塞 注1： Java 中 LinkedList 即为典型双端队列实现，不过它同时实现了 Queue 接口，也提供了栈的 push pop 等方法 注2： 不同语言，操作双端队列的方法命名有所不同，参见下表 操作 Java JavaScript C++ leetCode 641 尾部插入 offerLast push push_back insertLast 头部插入 offerFirst unshift push_front insertFront 尾部移除 pollLast pop pop_back deleteLast 头部移除 ...

栈 概述 计算机科学中，stack 是一种线性的数据结构，只能在其一端添加数据和移除数据。习惯来说，这一端称之为栈顶，另一端不能操作数据的称之为栈底，就如同生活中的一摞书 先提供一个栈接口 1234567891011121314151617181920212223242526272829303132public interface Stack<E> { /** * 向栈顶压入元素 * @param value 待压入值 * @return 压入成功返回 true, 否则返回 false */ boolean push(E value); /** * 从栈顶弹出元素 * @return 栈非空返回栈顶元素, 栈为空返回 null */ E pop(); /** * 返回栈顶元素, 不弹出 * @return 栈非空返回栈顶元素, 栈为空返回 null */ E peek(); /** * 判断栈是否为空 * @return 空返回 ...

队列 概述 计算机科学中，queue 是以顺序的方式维护的一组数据集合，在一端添加数据，从另一端移除数据。习惯来说，添加的一端称为尾，移除的一端称为头，就如同生活中的排队买商品 In computer science, a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence 先定义一个简化的队列接口 123456789101112131415161718192021222324252627282930313233public interface Queue<E> { /** * 向队列尾插入值 * @param value 待插入值 * @return 插入成功返回 tru ...