树 Tree

数据结构 · 有层次的非线性结构（二叉搜索树）

什么是树

前面的栈、队列、数组、链表都是线性的——元素排成一条线。树不一样：它从一个根节点出发，每个节点向下长出若干子节点，像一棵倒过来的树，是非线性的层次结构。

最常用的是二叉搜索树（BST）：每个节点最多两个孩子，且永远满足左子树都比它小、右子树都比它大。这条规矩让查找像猜数字一样高效——下面输入一个数试试插入或查找，看它怎么从根一路比较着往下走。

看见了吗——插入 35：和根 50 比，小，走左；和 30 比，大，走右；右边空了，就落在那。每下一层就排除掉一半，所以一棵平衡的 BST 查找只要 O(log n)。再点「中序遍历」——按左→根→右的顺序走一遍，吐出来的正好是升序，这是 BST 最漂亮的性质。

为什么会失衡 · 平衡的思想

BST 快，有个前提：树得长得开。可万一你按顺序插入 1 2 3 4 5 6 7——每个都比前一个大、全挂到右边，树就退化成一条链，高度变成 n，查找退回 O(n)，和链表一样慢，BST 的优势全没了。

平衡树（AVL、红黑树）就是来治这个的：一发现某一支太深，就旋转几下把树重新压扁，始终保持高度 ~O(log n)。下面同样 7 个值，切换看看「退化的链」和「平衡的树」差多少。

退化成链，查找 7 要老老实实走 7 步；平衡的树只要 3 步。值越多差距越夸张（n vs log n）。所以真实世界的有序 map / set、数据库索引，底层用的都是自平衡的树（红黑树、B 树），保证最坏情况也快。

树在哪里用

树把「一条线」升级成「会分叉的层次」。下一篇讲堆——一种用数组装的完全二叉树。