基本概念

树（Tree） 是一种非线性的分层数据结构，由节点（Node）和边（Edge）组成，满足以下条件：

1. 根节点（Root）：存在且唯一一个没有父节点的节点，作为树的起点。
2. 父子关系：除根节点外，每个节点有且仅有一个父节点。
3. 连通性：所有节点均通过边连通，即从根节点出发可通过路径到达任意节点。
4. 无环性：树中不存在环路，即没有从任一节点出发并沿边返回自身的路径。
5. 层次结构：节点按父子关系形成分层结构，根节点位于第一层，其子节点位于第二层，依此类推。

叶节点（Leaf）：没有子节点的节点
子树（Subtree）：以某节点为根，包含其所有后代节点的子结构
度（Degree）：节点的子节点数量；树的度为所有节点度的最大值。
节点的高度（height）：当前节点大到叶子节点的最长路径（边的数量）
节点的深度（depth）：根节点到当前节点的的边的数量
层级（level）：节点的深度 + 1
树高度：从根到最远叶节点的最长路径边数，根节点的高度，树高 = 节点高度 + 节点深度

- 阅读剩余部分 -

我们把时间复杂度为O(n)的排序算法称为线性排序。之所以能做到线性的时间复杂度，主要原因是，这样的算法是并非基于比较的排序算法，都不涉及元素之间的比较操作。但是如此高效是有代价的，线性排序的适用场景十分有限，条件苛刻。

- 阅读剩余部分 -

插入排序、冒泡排序和选择排序都是时间复杂度为O(n^2)的算法。小规模数据比较适合使用，实现相对简单，思想也比较符合直觉。

我们需要更优的，需要更加适合大规模数据的算法。

- 阅读剩余部分 -

排序在实际生产中是一种极其常见的操作，但是通常我们会使用现成的算法实现。更多时候是库或者第三方应用给你的数据本身就是有序的。对于大量数据的操作，优先进行排序是一个良好的习惯，在你后续的操作上都能从这个有序数据中受益。

- 阅读剩余部分 -

散列表（HashTable）

散列表也就是哈希表，是一种键值对（key-value pair）数据结构。散列表用的是数组支持按照下标随机访问数据的特性，所以散列表其实就是数组的一种扩展，由数组演化而来。可以说，如果没有数组，就没有散列表。

哈希表的本质是将键（key）通过散列函数获得散列值（哈希值）映射到数组的index上，使得我们可以利用上数组可以通过index随机访问数据的特性，通过key直接访问value。

- 阅读剩余部分 -