波仔
⚙️ 第四章 让内存化方为圆
📄 一句话概括

规则只有一句：小的往左、大的往右；每走一步甩掉一半，100 万条数据最多 20 次就能找到。

📝 本节和前面几节的关系

4.6 说链表找起来慢，这一节给出一个既能插删灵活、又能快速查找的结构，也是本章的收口。

一、为什么还要一棵树

到这儿已经有三种容器了，可都还差着点： 数组——按下标取飞快，但按值找要一个个比。 链表——插删方便，但连按下标取都做不到，找起来比数组还慢。 于是问题变成了：有没有一种摆法，找得又快、插删又不贵？ 把节点像树枝一样分叉摆开，就有了二叉查找树。

二、规矩只有一句：小的往左、大的往右

每个节点最多带两个孩子：比它小的往左走，比它大的往右走。 这条规矩一眼看去平平无奇，但它带来一个很强的性质： 沿着这条线走一步，就等于把剩下的数据砍掉一半。 因为往左走就意味着【右边那一整棵子树里的数全都不要了】——它们都比目标大。

三、效率：每步甩掉一半

砍一半再砍一半，这就是对数级：100 万条数据，最多只要 20 次。 顺序查找最坏要 100 万次，差距是五万倍。 插入也不贵：顺着同一条规矩走到空位，挂上去就行，走的步数同样是对数级。 查得快、插得快，这正是数组和链表各自缺的那一半。

四、坑：树会长歪

要是按从小到大的顺序插入，每个新节点都往右挂——树就退化成一根链子。 这时候找 80 要走 9 步，跟顺序查找一样慢。 所以树的效率全靠【长得匀不匀】，而不是【是不是树】。 现实中的补丁是各种自平衡树（AVL 树、红黑树）：发现歪了自动转一转。数据库和语言标准库里的有序字典，底层多半就是它们。

五、这一章到这里就圆了

回头看这一章的七个形状：内存本身一直是方方正正的一长串格子，从没变过。 变的只是你给它定的规矩：规定连续就是数组，规定哪头进出就是栈和队列，规定记下一个在哪就是链表，规定小的往左就是树。 章名说的【让内存化方为圆】，就是这个意思。 下一章换个方向：这串又快又小的格子，和又慢又大的磁盘之间，是怎么配合起来的。

六、动手 Demo：用二叉查找树高效地查找数据

规则一句话：小的往左、大的往右。每走一步就能甩掉一半数据。

class Node:
    def __init__(self, v):
        self.v, self.l, self.r = v, None, None

def insert(root, v):
    if root is None:
        return Node(v)
    if v < root.v:
        root.l = insert(root.l, v)
    else:
        root.r = insert(root.r, v)
    return root

def search(root, v):
    path, cur = (), root
    while cur is not None:
        path += (cur.v,)
        if v == cur.v:
            return path
        cur = cur.l if v < cur.v else cur.r
    return path

root = None
for v in (50, 30, 70, 20, 40, 60, 80, 10, 25):
    root = insert(root, v)
print("找 25 走这几步：", search(root, 25))

实跑输出：

--------------------------------------------------------------------
用二叉查找树高效地查找数据
--------------------------------------------------------------------

数组按值找要一个个看，二叉查找树的规则是**小的往左、大的往右**：

    每走一步就能甩掉一半数据

  数据量      顺序查找最多次数     二叉查找树最多次数
  ----------------------------------------------------
  15          15                   4
  127         127                  7
  1023        1023                 10
  1048575     1048575              20

  数据越多，差距越离谱：100 万个数据，顺序找最坏要 100 万次，树里最多 20 次。

  真建一棵树，插入顺序 [50, 30, 70, 20, 40, 60, 80, 10, 25]

    找 25  走了 4 步：50 -> 30 -> 20 -> 25
    找 80  走了 3 步：50 -> 70 -> 80

  但有个坑必须知道：**按顺序从小到大插入，树会退化成一根链子。**

    改成按 10 20 25 30 40 50 60 70 80 的顺序插入，找 80 要走 9 步。
    跟顺序查找一样慢了——**树的效率全靠【树长得匀不匀】。**

9 个数的树里找 25 走 4 步、找 80 走 3 步；顺序查找最坏要 9 步。 但按顺序插入会退化成链子，找 80 又变成 9 步——树长得匀不匀才是关键。

30 秒实验

  1. 在纸上按 5、3、8、2、4、7、9 的顺序画一棵二叉查找树，然后找 4 走了几步。
  2. 把插入顺序改成 2、3、4、5、7、8、9，重新画一遍，看形状差别有多大。

常见误区

  1. 以为只要是二叉查找树就一定快。长歪了就跟链表一样慢。
  2. 忘了【小的往左、大的往右】是唯一规矩。放反了整棵树都失去意义。
自测三问（点开对答案） 1. 二叉查找树的规矩是什么？ —— 每个节点：比它小的往左子树走，比它大的往右子树走。 2. 它为什么查得快？ —— 每比较一次就能排除掉一整棵子树，等于甩掉一半数据，复杂度是对数级。 3. 什么时候它会变慢？ —— 按有序数据插入时长成一条链，退化成链表，查找变成逐个比较。

相关笔记