标签 算法基础 下的文章

思想

二分查找的思想很常见也很简单，使用分治思想从左边（中间元素大于目标元素）或者从右边（中间元素小于目标元素）查找元素。在一个顺序表中查找等于X的元素的index，从中间元素开始匹配，如果等于则直接返回，如果小于目标元素，则向左边区间查找，如果大于目标元素则向右边查找。

- 阅读剩余部分 -

树的平衡性

平衡二叉树的严格定义是这样的：二叉树中任意一个节点的左右子树的高度相差不能大于 1。从这个定义来看，上一节我们讲的完全二叉树、满二叉树其实都是平衡二叉树，但是非完全二叉树也有可能是平衡二叉树。

平衡二叉查找树不仅满足上面平衡二叉树的定义，还满足二叉查找树的特点。发明平衡二叉查找树这类数据结构的初衷是，解决普通二叉查找树在频繁的插入、删除等动态更新的情况下，出现时间复杂度退化的问题。

所以，平衡二叉查找树中“平衡”的意思，其实就是让整棵树左右看起来比较“对称”、比较“平衡”，不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些，相应的插入、删除、查找等操作的效率高一些。

常见的平衡二叉查找树有：AVL树、Splay Tree（伸展树）、Treap（树堆）和红黑树等等。使用最广泛的是红黑树，从linux内核到jdk的HashMap等等都被广泛使用到。

- 阅读剩余部分 -

基本概念

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

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

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

- 阅读剩余部分 -

  1. 1
  2. 2