1. 树（Tree）

1.1. 定义

维基百科中的定义，在计算机科学中，树（英语：tree）是一种抽象数据类型（ADT）或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

每个节点都只有有限个子节点或无子节点；
没有父节点的节点称为根节点；
每一个非根节点有且只有一个父节点；
除了根节点外，每个子节点可以分为多个不相交的子树；
树里面没有环路(cycle)

1.2. 术语

节点的度：一个节点含有的子树的个数
树的度：一棵树中，最大的节点的度为树的度
叶节点或终端节点：
父节点：图2中，A 节点就是 B 节点的父节点
子节点：图2中，B 节点就是 A 节点的子节点
兄弟节点：图2中，B、C 两个节点的父节点是同一个节点，所以他们互称为兄弟节点
根节点：没有父节点的节点叫作根节点，也是就是图2中的节点 A
叶子节点：没有子节点的节点叫作叶子节点，如图2中的 D、E、F、G 都是叶子节点。

树的三个比较相似的概念：高度（Height）、深度（Depth）、层（Level）

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

1.3. 树的种类

1.3.1. 无序树

树中任意节点的子节点之间没有顺序关系，这种树称为无序树，也称为自由树；

1.3.2. 有序树

树中任意节点的子节点之间有顺序关系，这种树称为有序树；

二叉树：每个节点最多含有两个子树的树称为二叉树；
- 完全二叉树：对于一颗二叉树，假设其深度为d（d>1）。除了第d层外，其它各层的节点数目均已达最大值，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
  - 满二叉树：所有叶节点都在最底层的完全二叉树；
- 平衡二叉树（AVL树）：当且仅当任何节点的两棵子树的高度差不大于1的二叉树；
- 排序二叉树(二叉查找树（英语：Binary Search Tree))：也称二叉搜索树、有序二叉树；
霍夫曼树：带权路径最短的二叉树称为哈夫曼树或最优二叉树；
B树：一种对读写操作进行优化的自平衡的二叉查找树，能够保持数据有序，拥有多于两个子树。

2. 二叉树（Binary Tree）

2.1. 二叉树定义

二叉树（英语：Binary tree）是每个节点最多只有两个分支（即不存在分支度大于2的节点）的树结构。通常分支被称作“左子树”或“右子树”。

2.2. 特殊二叉树

2.2.1. 满二叉树

叶子节点全部都在最底层，并且每个节点都有两个子节点，如图6，这种二叉树就叫作满二叉树。

2.2.2. 完全二叉树

叶子节点都在最底下两层，最后一层的叶子节点都排列在最左边，除了最后一层，其他层的节点个数都达到最大，如图7，这种二叉树叫作完全二叉树。

2.3. 二叉树的存储

链式存储法：每个节点有三个字段，一个存储数据，另外两个存储指向左右子节点的指针。
顺序存储法：根节点存储在下标 i = 1 的位置，左子节点存储在下标 2 i = 2 的位置，右子节点存储在 2 i + 1 = 3 的位置。同理，B 节点的左子节点存储在 2 i = 2 2 = 4 的位置，右子节点存储在 2 i + 1 = 2 2 + 1= 5 的位置。节点 X 存储在数组下标为 i 的位置，下标 2 i 的位置存储的是左子节点，2 i + 1 存在的是右子节点。i/2 存储的就是父节点。根节点存储在下标为 1 的位置。

如果是非完全二叉树，会比较浪费数组的空间。大部分二叉树代码都是通过链式这种结构来存储。

3. 二叉查找树（Binary Search Tree）

在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

3.1. 查找操作

先取根节点，如果它等于我们要查找的数据，那就返回。如果要查找的数据比根节点的值小，那就在左子树中递归查找；如果要查找的数据比根节点的值大，那就在右子树中递归查找。如下图

3.1.1. 查找操作代码实现

// 递归算法，看以 Node 为根的二叉查找树是否包含e
func contains(n *Node, e interface{}) bool {
    if n == nil {
        return false
    }

    if util.Compare(n.e, e) == 0 {
        return true
    } else if util.Compare(e, n.e) < 0 {
        return contains(n.left, e)
    } else {
        return contains(n.right, e)
    }
}

3.2. 插入操作

要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

3.2.1. 插入操作代码实现

// 递归算法，插入元素e，返回插入新节点之后的二叉查找树的根
func (b *BST) add(n *Node, e interface{}) *Node {
    if n == nil {
        b.size ++
        return createNode(e)
    }

    if util.Compare(e, n.e) < 0 {
        n.left = b.add(n.left, e)
    } else if util.Compare(e, n.e) > 0 {
        n.right = b.add(n.right, e)
    }
    return n
}

3.3. 二叉查找树的遍历（深度优先遍历）

前序遍历（PreOrder）：先访问当前节点，再依次递归访问左右子节点
中序遍历（InOrder）：先递归访问左子节点，再访问当前节点，再递归访问右子节点
后序遍历（PostOrder）：先递归访问左右子节点，再访问当前节点

3.3.1. 遍历代码实现

// 递归算法，前序遍历 Node 为根的二叉查找树
func preOrder(n *Node) {
    if n == nil {
        return
    }

    fmt.Println(n.e)
    preOrder(n.left)
    preOrder(n.right)
}

// 递归算法，中序遍历 Node 为根的二叉查找树
func inOrder(n *Node) {
    if n == nil {
        return
    }

    inOrder(n.left)
    fmt.Println(n.e)
    inOrder(n.right)

}

// 递归算法，后序遍历 Node 为根的二叉查找树
func postOrder(n *Node) {
    if n == nil {
        return
    }

    postOrder(n.left)
    postOrder(n.right)
    fmt.Println(n.e)

}

注：中序遍历二叉搜索树可以输出有序的数据序列，时间复杂度是 O(n)，非常高效。后序遍历是先遍历左右子节点再遍历本身，内存的释放可以采用后序遍历的方式。

3.4. 层序遍历（广度优先遍历）

层序遍历是一种广度优先的遍历方式,先遍历根节点这一层,再遍历第二层,依次这样从上到下,从左到右。利用队列先入先出的特性。根节点入队列，开始循环判断，条件是队列是否为空，先处理当前节点，然后出队列（此时队列为空），看看当前节点有没有左右子节点，如果有入队列（此时队列不为空，进入下一层循环）以此类推。

3.4.1. 层序遍历代码实现

func (b *BST) LevelOrder() {
    queue := LoopQueue.New(30)
    queue.Enqueue(b.root)
    for ! queue.IsEmpty() {
        cur := queue.Dequeue().(*Node)
        fmt.Println(cur.e)

        if cur.left != nil {
            queue.Enqueue(cur.left)
        }
        if cur.right != nil {
            queue.Enqueue(cur.right)
        }
    }
}

3.5. 删除最大值、最小值

// 删除二叉查找树最小值所在的节点，返回最小值
func (b *BST) RemoveMin() interface{} {
    ret := b.Minimum()
    b.root = b.removeMin(b.root)
    return ret
}

// 递归算法，删除以 Node 为根的二叉查找树中最小 节点
// 返回删除节点后新的二叉查找树的根
func (b *BST) removeMin(n *Node) *Node {
    if n.left == nil {
        right := n.right
        b.size--
        return right
    }
    n.left = b.removeMin(n.left)
    return n
}

// 删除二叉查找树最大值所在的节点，返回最大值
func (b *BST) RemoveMax() interface{} {
    ret := b.Maximum()
    b.root = b.removeMax(b.root)
    return ret
}

// 递归算法，删除以 Node 为根的二叉查找树中最大节点
// 返回删除节点后新的二叉查找树的根
func (b *BST) removeMax(n *Node) *Node {
    if n.right == nil {
        left := n.left
        b.size--
        return left
    }
    n.right = b.removeMax(n.right)
    return n
}

3.6. 二叉查找树删除

根据要删除节点的子节点个数的不同，我们需要分三种情况来处理：

如果要删除的节点没有子节点，我们只需要直接将父节点中，指向要删除节点的指针置为 null。比如图14中的删除节点 54。
如果要删除的节点只有一个子节点（只有左子节点或者右子节点），我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图14中的删除节点 13。
如果要删除的节点有两个子节点，这就比较复杂了。我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图14中的删除节点 18。

3.6.1. 二叉查找树删除代码实现

// 从二叉查找树中删除元素为 e 的节点
func (b *BST) Remove(e interface{}) {
    b.root = b.remove(b.root, e)
}

// 递归算法，删除以 Node 为根的二叉查找树中值为 e 的节点
// 返回删除节点后新的二分搜索树的根
func (b *BST) remove(n *Node, e interface{}) *Node{
    if n == nil {
        return nil
    }

    if util.Compare(e, n.e) < 0 {
        n.left = b.remove(n.left, e)
        return n
    } else if util.Compare(e, n.e) > 0 {
        n.right = b.remove(n.right, e)
        return n
    } else {
        if n.left == nil {
            right := n.right
            n.right = nil
            b.size--
            return right
        }

        if n.right == nil {
            left := n.left
            n.left = nil
            return left
        }
        // 待删除节点左右子节点都不为空
        // 找到比待删除节点大的最小节点，即待删除节点右子树的最小节点
        // 用这个后稷节点代替待删除的节点
        successor := minimum(n.right)
        successor.right = b.removeMin(n.right)
        successor.left = n.left
        n.left = nil
        n.right = nil
        return successor
    }
}

3.7. 二叉查找树的顺序性

查找前驱节点
查找后继节点
floor
ceil
二叉查找树的RANK
二叉查找树的SELECT
支持重复元素的二叉查找树
- 把大于节点的放在右子节点，小于等于当前节点的放在左子节点。
- 为 Node 增加一个域，用这个域来标记当前节点的个数

3.8. 二叉查找树的局限性

如图15所示，对于同一组数据，构造了三种二叉查找树。但这三种二叉查找树的查找、插入、删除操作的执行效率是不一样的。当数据的插入顺序接近有序的时候，二叉查找树就有可能退化成了链表，时间复杂度从logn又变成了n。

显然，极度不平衡的二叉查找树，它的查找性能肯定不能满足我们的需求。我们需要构建一种不管怎么删除、插入数据，在任何时候，都能保持任意节点左右子树都比较平衡的二叉查找树。

平衡二叉树的实现：

红黑树
2-3树
AVL树

4. 平衡二叉查找树

4.1.1. 定义

1962年，Adelson-Velsikii和Landis提出了一种结点在高度上相对平衡的二叉查找树，又称为AVL树。其平均和最坏情况下的查找时间都是O(logn)。同时，插入和删除的时间复杂性也会保持O(logn)，且在插入和删除之后，在高度上仍然保持平衡。AVL树又称为平衡二叉树，即Balanced Binary Tree或者Height-Balanced Tree，它或者是一棵空二叉树，或者是具有如下性质的二叉查找树：其左子树和右子树都是高度平衡的二叉树，且左子树和右子树的高度之差的绝对值不超过1。如果将二叉树上结点的平衡因子BF（Balanced Factor）定义为该结点的左子树与右子树的高度之差，根据AVL树的定义，AVL树中的任意结点的平衡因子只可能是-1（右子树高于左子树）、0或者1（左子树高于右子树），在某些图中也会表示为绝对高度差，即0，1，2这种形式，请注意理解。

type Node struct {
    key         interface{}
    value       interface{}
    left, right *Node
    height      int
}

4.1.2. 失衡调整与处理详解

每次在插入新节点之后都会找到离新插入节点最近的非平衡叶节点，然后对其进行旋转操作以使得树中的每个节点都处于平衡状态。

// 对节点y进行向右旋转操作，返回旋转后新的根节点x
//        y                              x
//       / \                           /   \
//      x   T4     向右旋转 (y)        z     y
//     / \       - - - - - - - ->    / \   / \
//    z   T3                       T1  T2 T3 T4
//   / \
// T1   T2
func (a *AVLTree) rightRotate(y *Node) *Node {
 x := y.left
 T3 := x.right

 // 向右旋转过程
 x.right = y
 y.left = T3

 // 更新 height
 y.height = int(math.Max(float64(a.getHeight(y.left)), float64(a.getHeight(y.right)))) + 1
 x.height = int(math.Max(float64(a.getHeight(x.left)), float64(a.getHeight(x.right)))) + 1

 return x
}

// 对节点y进行向左旋转操作，返回旋转后新的根节点x
//    y                             x
//  /  \                          /   \
// T1   x      向左旋转 (y)       y     z
//     / \   - - - - - - - ->   / \   / \
//   T2  z                     T1 T2 T3 T4
//      / \
//     T3 T4
func (a *AVLTree) leftRotate(y *Node) *Node {
 x := y.right
 T2 := x.left

 // 向左旋转过程
 x.left = y
 y.right = T2

 // 更新 height
 y.height = int(math.Max(float64(a.getHeight(y.left)), float64(a.getHeight(y.right)))) + 1
 x.height = int(math.Max(float64(a.getHeight(x.left)), float64(a.getHeight(x.right)))) + 1

 return x
}

LR（左侧的右侧）

// T1 < x < T2 < z < T3 < y < T4
//     y                             y
//    /  \                          /  \
//   x   T4      向左旋转 (x)        z   T4
//  / \        - - - - - - - ->   / \        同LL 右旋
// T1 z                          x  T3  
//   / \                        / \
//  T2 T3                      T1 T2
if balanceFactor > 1 && a.getBalanceFactor(n.left) < 0 {
     n.left = a.leftRotate(n.left)
     return a.rightRotate(n)
 }

// T1 < y <T2 < z < T3 < x < T4 
//      y                               y
//     / \                             / \
//    T1  x       向右旋转 (x)          T1  z   同RR 左旋
//       / \     - - - - - - - ->        / \ 
//      z   T4                          T2  x    
//     / \                                 / \
//    T2  T3                              T3 T4
if balanceFactor < -1 && a.getBalanceFactor(n.right) > 0 {
     n.right = a.rightRotate(n.right)
     return a.leftRotate(n)
 }

4.2. 平衡二叉查找树删除操作

此处省略

5. 2-3树与红黑树

5.1. 2-3树定义

和二叉树不一样，2-3树运行每个节点保存1个或者两个的值。对于普通的2节点(2-node)，他保存1个key和左右两个自己点。对应3节点(3-node)，保存两个Key，2-3查找树的定义如下：一棵不为空的 2-3树主要由以下节点构成：

2-3树满足二分搜索树（BST）的基本性质，2-3树是一棵绝对平衡的树。

5.2. 2-3树添加节点

插入一个 2-节点

插入一个 3-节点，没有父亲节点
插入一个 3-节点，同时父亲节点为 2-节点
插入一个 3-节点，同时父亲节点为 3-节点

将一个4-节点分解为一棵2-3树有 6 种情况

2-3树的生长是由下往上的，也就是说，没插入一个新的节点，都先与叶子节点相融合，然后再根据不同的情况向上做调整。

下面是不断插入节点构造一棵 2-3树的过程：

5.3. 2-3树与红黑树的等价性

将特殊的边的信息存放在节点上。引入红色节点表示：它与它的父亲在 2-3树中是一个 2-节点。

2-节点对应的红黑树

3-节点对应的红黑树

现在我们来根据一个 2-3树来绘制一棵红黑树。

红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：

红色节点向左倾斜一个节点不可能有两个红色链接整个书完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。

通过上图可以清晰的知道，将红链接画平后，一棵红黑树就是一棵 2-3树。

「算法导论」中对红黑树的定义：

每个节点或者是红色的，或者是黑色的
根节点是黑色的
每一个叶子节点（最后的空节点）是黑色的 -Every leaf(NIL)is black
如果一个节点是红色的，那么它的孩子节点是黑色的
从任意一个节点到叶子节点，经过的黑色节点的个数是相同的

红黑树是保持“黑平衡”的二叉树，严格意义来说，红黑树不是一棵平衡二叉树。

红黑树的最大高度：2logn => 时间复杂度（增删改查）：O(logn) 红黑树不会退化成为一个链表。

红黑树的最大高度要高于 AVL 树，在红黑树上进行元素的查找，相比于 AVL 树会慢一些。但是这不影响红黑树成为一个伟大的数据结构，甚至比 AVL 树还要重要、还要常用。

红黑树的添加元素、删除元素，相比于 AVL 树来说，要更加快速。对于数据结构来说，如果存储的元素经常需要添加/删除的话，相应的使用红黑树就是一个更好的选择。但是如果在数据结构中存储的数据近乎不会变动，创建完成后，主要进行查询/修改操作，那么选择 AVL 树就是一个很好的选择。

6. B树

6.1. B树定义

B树和平衡二叉树稍有不同的是B树属于多叉树又名平衡多路查找树（查找路径不只两个），数据库索引技术里大量使用者B树和B+树的数据结构。

排序方式：所有节点关键字是按递增次序排列，并遵循左小右大原则；
子节点数：非叶节点的子节点数>1，且<=M ，且M>=2，空树除外（注：M阶代表一个树节点最多有多少个查找路径，M=M路,当M=2则是2叉树,M=3则是3叉）；
关键字数：枝节点的关键字数量大于等于ceil(m/2)-1个且小于等于M-1个（注：ceil()是个朝正无穷方向取整的函数如ceil(1.1)结果为2);
所有叶子节点均在同一层、叶子节点除了包含了关键字和关键字记录的指针外也有指向其子节点的指针只不过其指针地址都为null对应下图最后一层节点的空格子;

最后我们用一个图和一个实际的例子来理解B树（这里为了理解方便我就直接用实际字母的大小来排列C>B>A）

6.2. B树查询

如上图我要从上图中找到E字母，查找流程如下

获取根节点的关键字进行比较，当前根节点关键字为M，E<M（26个字母顺序），所以往找到指向左边的子节点（二分法规则，左小右大，左边放小于当前节点值的子节点、右边放大于当前节点值的子节点）；
拿到关键字D和G，D<E<G 所以直接找到D和G中间的节点；
拿到E和F，因为E=E 所以直接返回关键字和指针信息（如果树结构里面没有包含所要查找的节点则返回null）；

6.3. B树的插入

定义一个5阶树（平衡5路查找树;），现在我们要把3、8、31、11、23、29、50、28 这些数字构建出一个5阶树出来;

节点拆分规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须<=5-1（这里关键字数>4就要进行节点拆分）；
排序规则：满足节点本身比左边节点大，比右边节点小的排序规则;

先插入 3、8、31、11

再插入23、29

再插入50、28

6.4. B树的删除

节点合并规则：当前是要组成一个5路查找树，那么此时m=5,关键字数必须大于等于ceil（5/2）（这里关键字数<2就要进行节点合并）；
满足节点本身比左边节点大，比右边节点小的排序规则;
关键字数小于二时先从子节点取，子节点没有符合条件时就向向父节点取，取中间值往父节点放；

6.5. B树特点

B树相对于平衡二叉树的不同是，每个节点包含的关键字增多了，特别是在B树应用到数据库中的时候，数据库充分利用了磁盘块的原理（磁盘数据存储是采用块的形式存储的，每个块的大小为4K，每次IO进行数据读取时，同一个磁盘块的数据可以一次性读取出来）把节点大小限制和充分使用在磁盘快大小范围；把树的节点关键字增多后树的层级比原来的二叉树少了，减少数据查找的次数和复杂度;

7. B+树

7.1. B+树定义

B+树是B树的一个升级版，相对于B树来说B+树更充分的利用了节点的空间，让查询速度更加稳定，其速度完全接近于二分法查找。为什么说B+树查找的效率要比B树更高、更稳定；我们先看看两者的区别

B+跟B树不同B+树的非叶子节点不保存关键字记录的指针，只进行数据索引，这样使得B+树每个非叶子节点所能保存的关键字大大增加；
B+树叶子节点保存了父节点的所有关键字记录的指针，所有数据地址必须要到叶子节点才能获取到。所以每次数据查询的次数都一样；
B+树叶子节点的关键字从小到大有序排列，左边结尾数据都会保存右边节点开始数据的指针。
非叶子节点的子节点数=关键字数（来源百度百科）（根据各种资料这里有两种算法的实现方式，另一种为非叶节点的关键字数=子节点数-1（来源维基百科)，虽然他们数据排列结构不一样，但其原理还是一样的Mysql 的B+树是用第一种方式实现）;

百度百科算法结构示意图

维基百科算法结构示意图

7.2. B+树特点

B+树的层级更少：相较于B树B+每个非叶子节点存储的关键字数更多，树的层级更少所以查询数据更快；
B+树查询速度更稳定：B+所有关键字数据地址都存在叶子节点上，所以每次查找的次数都相同所以查询速度要比B树更稳定;
B+树天然具备排序功能：B+树所有的叶子节点数据构成了一个有序链表，在查询大小区间的数据时候更方便，数据紧密性很高，缓存的命中率也会比B树高。
B+树全节点遍历更快：B+树遍历整棵树只需要遍历所有的叶子节点即可，，而不需要像B树一样需要对每一层进行遍历，这有利于数据库做全表扫描。

B树相对于B+树的优点是，如果经常访问的数据离根节点很近，而B树的非叶子节点本身存有关键字其数据的地址，所以这种数据检索的时候会要比B+树快。

本文摘自: 树,二叉树,平衡二叉树,红黑树,B树等逐步深入了解