树

• 根节点
• 子节点

• 叶子节点

  二叉树

• 二叉树是每个节点最多有两个子节点的树。

• 叶子节点无子节点，，二叉树的根节点或者内部节点有一个或者两个字节点。

二叉查找树

• 二叉查找树也称为二叉排序树
• 二叉查找树专门用于查找（二分查找），增加如下规则以实现二分
  • 若左数不空，左边树的所有节点都小于父节点；若右树不空，右边树的所有节点都大于父节点
    • 这样任意3个直接相连的三角也是二叉查找树
  • 插入时如果是相同，则往右边插

• 二叉查找树最好的情况是查找的次数小于二叉树的高度（下面高度4）
  • 但是如果都是偏离根节点的值，就变成了左右不对称树，这时就变成了顺序查找。这明显是能进行优化的

平衡二叉树

• 又称为AVL树，可以看成二叉查找树的升级。(即采用平衡的方法来解决二叉树的不足，尽量左右平衡)
• 左右子树高度差不超过1
  • 如果插入时高度差超过1，则把失衡的一边的子树根节点变为整个树的根节点

• 链接

  红黑树

• 红黑树属于平衡二叉树的一种实现，红黑树不再遵循高度差超过1就旋转的操作

  • 节点是红色或黑色。
  • 根节点是黑色。
  • 每个叶子节点都是黑色的空节点（NIL节点）。
  • 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
• 以上实现了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

• 红黑树变化时如果打破规则，有2种方法解决：变色/旋转，旋转又分为左旋/右旋
  • 如果能直接变色可以变色解决，不行的话就先旋转后变色

• 红黑树放弃了追求完全平衡，追求大致平衡，在与平衡二叉树的时间复杂度相差不大的情况下，保证每次插入最多只需要三次旋转就能达到平衡，实现起来也更为简单。

• 平衡二叉树追求绝对平衡，条件比较苛刻，实现起来比较麻烦，每次插入新节点之后需要旋转的次数不能预知。

  B树&B+树

• B 树也称 B-树,全称为 多路平衡查找树 ，B+ 树是 B 树的一种变体。B 树和 B+树中的 B 是 Balanced （平衡）的意思。

• 目前大部分数据库系统及文件系统都采用 B-Tree 或其变种 B+Tree 作为索引结构。
• b-与b+的区别：
  • B 树的所有节点既存放键(key) 也存放 数据(data)，而 B+树只有叶子节点存放 key 和 data，其他内节点只存放 key。
  • B 树的叶子节点都是独立的;B+树的叶子节点有一条引用链指向与它相邻的叶子节点。
  • B 树的检索的过程相当于对范围内的每个节点的关键字做二分查找，可能还没有到达叶子节点，检索就结束了。而 B+树的检索效率就很稳定了，任何查找都是从根节点到叶子节点的过程，叶子节点的顺序检索很明显。