二叉树

二叉树：在二叉树中，任意节点的度<=2

二叉树分类：

  • 二叉查找树
  • 平衡二叉树
  • 红黑树

二叉查找树

  1. 每一个节点上最多有两个子节点
  2. 任意节点左子树上的值都小于当前节点
  3. 任意节点右子树上的值都大于当前节点

小的存左边，大的存右边，一样的不存

遍历方式：

  1. 前序遍历：当前节点，左子节点，右子节点
  2. 中序遍历：左子节点，当前节点，右子节点
  3. 后序遍历：左子节点，右子节点，当前节点
  4. 层序遍历：一层一层地去遍历

平衡二叉树

任意节点左右字数高度差不超过1

旋转机制

  • 左左 -> 右旋
  • 左右 -> 局部左旋再右旋
  • 右右 -> 左旋
  • 右左 -> 局部右旋再左旋

红黑树

添加节点的规则：

  1. 每一个节点是红色或黑色
  2. 根节点必须是黑色
  3. 叶节点（Nil）是黑色
  4. 两个红色节点不能相连
  5. 任意节点到所有后代叶节点的简单路径上，黑色节点数量相同

节点添加规律：

默认添加的节点是红色的

  • 根

​ 直接变成黑色

  • 非根

    • 父黑

      不需要任何操作

    • 父红

      • 叔叔红
        • 将父节点设置为黑，叔叔节点设置为黑
        • 祖父节点设置为红
        • 如果祖父节点是根，再变回红
        • 如果祖父节点非根，再将祖父节点设置为当前节点判断
      • 叔叔黑，当前节点为父的右子节点
        • 把父节点作为当前节点并左旋，再进行判断
      • 叔叔黑，当前节点为父的左子节点
        • 将父节点设置为黑
        • 将祖父节点设置为红
        • 以祖父节点为支点右旋