树的遍历方式，这里的前中后指的是根节点的位置。
image.png

红黑树

红黑树一颗 BST，并且有以下特点：

  1. 每个结点是红色或黑色
  2. 根结点是黑色
  3. 红色的子节点不能是红色
  4. 每条 root-NIL 路径中包含的黑色结点数量相同

    平衡二叉树

    有多种实现方式，例如红黑树，AVL树，B树

左旋

image.png

左旋可以把它理解为一棵树逆时针旋转，然后再排序，例如
原树 -> 左旋 -> 再排序
image.png image.png image.png

同理，右旋可以把它理解为一棵树逆时针旋转，然后再排序，例如
原树 -> 右旋 -> 再排序
image.png image.png image.png

左旋、右旋改变了子树的高度，旋转的时间复杂度为O(1)。

二叉树

  1. 每个节点最多只有两个子节点（也就是两个度）

完全二叉树

只有最右边的节点缺失，才符合完全二叉树的定义。
image.png

满二叉树

一棵二叉树中，如果不存在度为 1 的节点，那么就是满二叉树。

度，一个节点指向一个节点，这就是一个度，指向 N 个节点就是 N 个度

image.png

完美二叉树

每一层都是满的
image.png

二叉搜索树

节点的大小关系：左节点 < 根节点 < 右节点

前序遍历，中序遍历，后序遍历，这里的前中后指的是根节点的顺序。

其中，中序遍历的结果是升序的。
image.png

深度优先

如下图深度优先，从根节点开始遍历每个节点
image.png
image.png