数据结构-二叉树

Summary

前面的数组、链表、栈、队列都是"一条线"——每个元素最多一个前驱、一个后继。但现实世界大量是层次关系:文件系统的目录树、公司的组织架构、HTML 的 DOM、区块链的 Merkle 树。树就是描述这种"一对多"层次关系的结构。更重要的是,树把查找从线性结构的 O(n) 压到了 O(log n)——这是它存在的核心价值。这个结构应用得很广泛，需要重点学习。

树是什么

树是 n 个节点的有限集合,它满足:

有且仅有一个根节点(root),没有父节点。
除根外,每个节点有且仅有一个父节点;一个节点可以有 0 个或多个子节点(child)。
没有环——从根出发不会绕回自己。

换句话说,树是一种特殊的图:连通、无环、n 个节点恰好 n-1 条边。它的"非线性"体现在:一个节点可以有多个后继(孩子),所以数据是分叉展开的,不再是一条线。

            根 root
           /   |   \
          A    B    C        ← A、B、C 是根的孩子,根是它们的父
         / \        |
        D   E       F         ← D、E、F 是叶子(no child)

树的关键词

用上面这棵树对照:

节点的度(degree):该节点的孩子个数。根的度是 3,A 的度是 2,D 的度是 0。
叶子节点(leaf):度为 0 的节点(B、D、E、F)。
深度(depth):从根到该节点的边数(根深度 0)。
高度(height):从该节点到最深叶子的边数;树的高度=根的高度。上图高度为 2。
层(level):通常根为第 1 层,往下递增。
子树(subtree):任意节点连同它下面所有节点,自成一棵树。

树上大多数操作(查找、插入)的代价正比于高度 h。树越"矮胖平衡",h 越接近 log n,操作越快;越"高瘦"(退化成链),h 越接近 n,越慢。“如何让树保持矮"是二叉树的精髓

二叉树(Binary Tree)——最重要的一类树

每个节点最多两个孩子,分别叫左孩子和右孩子,且左右有序(不能交换)。

两种特殊形态

满二叉树(full/perfect):每一层都填满,叶子全在最底层。高度 h 的满二叉树有 2^(h+1) - 1 个节点。
完全二叉树(complete):除最后一层外都填满,且最后一层的节点靠左连续排列。这个"靠左连续"的性质极其重要——它让树可以用数组紧凑存储。

满二叉树:            完全二叉树(最后一层靠左):
     1                    1
   /   \                /   \
  2     3              2     3
 / \   / \            / \   /
4   5 6   7          4   5 6           ← 7 的位置空着也没关系,只要靠左连续

代码实现

使用链表的方式实现是最高效快捷的，代码如下：

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

完全二叉树使用数组的形式也是可以实现的，每个下标对应的节点是

对下标 i(从 0 开始)的节点:
  左孩子 = 2i + 1
  右孩子 = 2i + 2
  父亲   = (i - 1) / 2

遍历

树的遍历是按照某种特定的顺序进行访问，通常分为两大类：深度遍历、广度遍历

深度遍历

有三种遍历顺序

前序遍历：根 -> 左 -> 右
中序遍历：左 -> 根 -> 右对于二叉搜索树，中序遍历就是升序遍历
后序遍历：右 -> 左 -> 根使用场景：计算目录大小、释放子树、表达式求值。

使用递归可以很方便的写出上述遍历，代码如下：

func Traversal(root *TreeNode) {
    if root == nil {
        return
    }
    fmt.Println(root.Val)      // 根 —— 把这行移到下面一行是中序, 移到最后是后序
    Traversal(root.Left)  // 左
    Traversal(root.Right) // 右
}

广度遍历

一层一层从上到下、从左到右访问。

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }
    var res [][]int
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        n := len(queue) // 获取当层节点数量
        level := make([]int, 0, n)
        for i := 0; i < n; i++ {
            node := queue[0]
            queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        res = append(res, level) // 每一层单独成组
    }
    return res
}

二叉搜索树（BST）

普通的树，节点之间是没有任何规律的，进行查找还需要遍历，效率接近O(n)。

二叉搜索树是一个特殊的树，它的节点遵循，左节点的值小于 < 父节点，右节点的值 > 父节点的值，这使得查询的效率提成到了O(h)树高 | log(n)，类似二分查找。

func (t *TreeNode) Search(target int) *TreeNode {
    cur := t
    for cur != nil {
        switch {
        case target == cur.Val:
            return cur
        case target < cur.Val:
            cur = cur.Left  // 目标更小,去左子树
        default:
            cur = cur.Right // 目标更大,去右子树
        }
    }
    return nil
}

删除操作

删除是此数最麻烦的操作，为了保证遵循的规则，删除分三种情况：

叶子节点，直接删除就可以了
有一个子节点，直接让叶子节点变成自己
有两个字节点，删除时，需要找到右子树里最小的节点(中序后继)或左子树里最大的(中序前驱),用它的值替换自己,再去删那个后继/前驱的节点(它必然最多一个孩子,转化为情况 1 或 2)。

代码如下：

func (node *TreeNode) Delete(value int) *TreeNode {
	if node == nil {
		return nil
	}
	if value < node.Value {
		node.Left = node.Left.Delete(value)
	} else if value > node.Value {
		node.Right = node.Right.Delete(value)
	} else {
		if node.Left == nil {
			return node.Right
		} else if node.Right == nil {
			return node.Left
		}
		minRight := node.Right.findMin() // 找到右节点中最小的 // 中序前继，找到左节点中最大的子节点 maxLeft := node.Left.findMax() 
		node.Value = minRight.Value                         // node.Value = maxLeft.Value
		node.Right = node.Right.Delete(minRight.Value)      // node.Left = node.Left.LeftDelete(maxLeft.Value)
	}
	return node
}

func (node *TreeNode) findMin() *TreeNode {
	current := node
	for current.Left != nil {
		current = current.Left
	}
	return current
}

func (node *TreeNode) findMax() *TreeNode {
	current := node
	for current.Right != nil {
		current = current.Right
	}
	return current
}

测试时，可以使用下面的结构构建树：

删除50这个node，最终40会提升上去。30的这个node的右节点是nil。

极端情况

二叉搜索树的搜索复杂度 O(log n) 是有前提的——树必须是平衡的。如果按已经有序的数据依次插入(1,2,3,4,5……)，每次都插到右边，树就退化成一根"只有右孩子的链”,高度 h=n,查找退回 O(n),和链表没区别，如下：

所以针对涂上情况，出现了平衡树

平衡二叉树

针对上述情况导致数长歪了，那就在每次删除插入之后，自动调整，保证子树的高度不超过某个上限，把高度牢牢控制在O（log n），调整的核心手段是旋转-通过局部的左旋转和右旋转，在保证BST的性质下降低高度。常用的结构有：

AVL树：属于规则最严格的树，任意节点的左右子树高度差<=1。查找最快，但每次插入和删除旋转调整频繁。
红黑树：对平衡的规则要求稍微放宽了一些，插入删除调整的最少，也是最常用的平衡树（用红/黑规则保证最长路径≤ 2×最短路径）。
B 树/ B+ 树：一个节点可以储存多个子节点，让树更矮胖，极少磁盘IO，这种树在数据库中经常使用。

B 树 / B+ 树

之前演示的树都是按照放在内存里面进行的测试，但如果把树放到磁盘上，这些树就会很吃力了，因为磁盘IO是有上限的。总所周知，内存随机访问是很快的，可能也就几纳秒，磁盘一次随机访问的时间可能是几毫秒，差了很多倍。访问树时，没往下走一层，可能就需要一次磁盘IO，一颗存了10 万条记录的二叉树/平衡树，访问叶子节点，需要的IO次数可能超过你的想象。

而针对这类情况，解决方法也是有的，那就是让树变得矮胖，把一个节点只有两个子节点改成可以拥有多个节点，树的高度就直接塌下来了，这个就是B 树。

一个节点存一批有序的键 + 多个孩子指针,不再是二叉树。一个节点的大小正好对齐一个磁盘页(通常 4KB/16KB),这样"读一个节点 = 一次磁盘 IO"最划算——一次 IO 就把几百个键捞进内存，并且数据全部下沉到叶子节点，叶子节点使用双向链表串起来，这个就是B+ 树。
所有叶子在同一层(严格平衡),查找/插入/删除都是 O(logₘ n),这里的底数 m(路数/扇出)是几百上千,所以树高极矮。
算一笔账:扇出 1170 的 B+ 树,3 层就能索引约 2000 万条记录——查任意一条,最多 3 （计算： log₁₁₇₀(2000万) ≈ 3）次磁盘 IO。对比二叉树的 25（计算：log₂(2000万) ≈ 25）次磁盘IO,这就是数据库索引选它的根本原因。

扇出 1170 这个数字不是大风刮来的，是计算出来的，一个磁盘页，按照16KB进行计算，假设主键是bigint，8字节，子节点指针6字节，一条索引项是14字节， 16384 / 14 = 1170，三层树的结构就可以包含

1 层:1170
2 层:1170² ≈ 137 万
3 层:1170³ ≈ 16 亿

       B+ 树(3 阶示意,真实场景每节点几百个键):

              [ 10 | 20 ]                  ← 内部节点:只放"路标"键 + 孩子指针
             /    |     \
      [1|4|8] [11|15] [22|30]              ← 叶子:放全部真实数据
        ↕       ↕       ↕
       叶子之间用链表串起来 → 范围查询顺着链走,不用回树上跳

B 树和 B+ 树的区别大致如下：

    B 树:  [key|data|key|data|...]     一页塞不下几条
    B+树:  [key|ptr|key|ptr|...]       一页塞 1170 条

并不是所有的搜索引擎都用B+ 树。像LevelDB这种使用的是LSM-Tree（日志结构合并树）- 把随机写变成顺序写（先写内存memtable，再批量写到磁盘中的有序文件中）。使用：读多写少用 B+ 树, 写多读少用 LSM-Tree。

Trie(前缀树 / 字典树)

Trie 是一种多叉树,专门用来高效存储和检索字符串集合,尤其擅长前缀匹配。

思路:把字符串的每个字符作为一条边,从根到某节点的路径就拼成一个前缀。 公共前缀的字符串共享同一段路径。

存入 {"cat", "car", "card", "dog"}:

        (root)
        /     \
       c       d
       |       |
       a       o
      / \      |
     t   r     g
    (end)|
         (end)
         |
         d
        (end)