概念：

  • 根节点
  • 子节点
  • 叶子节点
  • 节点的高度：节点到叶子节点的最长路径（边数）
  • 节点的深度：根节点到这个节点所经历的边的个数
  • 节点的层数：节点的深度+1

  • 树的高度：根节点的高度

    二叉树（binary tree）

    注意点：

  • 并不要求每个节点都有两个子节点

    分类：

  • 满二叉树：所有叶子节点都在最底层，每个节点都有两个子节点

  • 完全二叉树：叶子节点都在最底下两层，最后一层节点都靠左排列，除了最后一层，其他层的节点都达到最大

    1. - 当是完全二叉树的时候，使用基于数组的的存储方式，最省内存

    如何存储：

  • 基于指针或者引用的二叉链式存储

  • 基于数组的顺序存储

    二叉树的遍历

  • 前序遍历

  • 中序遍历
  • 后序遍历

二叉查找树（binary search tree）

概念：任意一个节点，其左子树的每个节点的值小于这个节点的值，而右子树的值都大于这个节点的值

特点：

  • 快速查找
  • 快速删除
  • 快速插入
  • 中序遍历，可以输出有序的数据序列，复杂度为O(n)
  • 每个节点可以通过链表或者可动态扩容的数组，将值相同的数据存放在一个节点上

  • 复杂度O(logn)

    平衡二叉查找树

    概念：任意一个节点的左右子树高度相差不能超过1

    发明的原因：避免树在频繁的增删操作后，复杂度变高
    分类：

  • 红黑树

  • 伸展树
  • 树堆

红黑树

定义：红黑树的节点一类被标记为黑色，一类被标记为红色

  • 根节点为黑色
  • 叶子结点不存储数据（都是黑色节点，为了简化代码实现而设置）
  • 红色节点被黑色节点隔开
  • 每个节点，从任何节点出发到达其可达的任意叶子结点，都包含相同数目的黑色节点

性能分析:红黑树高度仅仅比高度avl树高度（log）大了一倍，性能下降的不多。avl树是一种高度平衡的二叉树，所以查找效率非常高，但是为了维持这种高度平衡，每次插入、删除就需要调整，代价较大。红黑树只是做到了近似平衡，从维护角度，成本较低。

实现（比较复杂，未看）：

  • 左旋和右旋
  • 改变颜色

递归树

用途：分析时间复杂度