树

树是从线性结构迈出的第一大步。数组或链表把数据排成一条直线，而树则会分叉：每个元素（称为节点）可以指向它下方的多个节点。这天然地刻画了层次关系——文件系统、组织结构图、棋局中的着法——一切从单一起点向外发散的事物。

这套术语值得一次学会、终身受用。最顶端唯一的节点称为根。指向其他节点的节点是父节点，被它指向的是子节点。没有子节点的节点叫叶子。树的高度是从根到某个叶子最长路径上的边数，而某个节点的深度是它到根的距离。关键在于：树中没有环——你顺着子节点一直走，永远不会回到出发点；除根以外的每个节点都恰好有一个父节点。

树之所以重要，是因为它的分叉形状能让操作变快。如果一棵树保持枝繁叶茂、又矮又宽，而不是又细又长，那么你只需大约 O(log n) 步就能到达任意节点，而不是 O(n)——这正是让二分查找变快的同一个对数级好处。本节中的大多数结构（查找树、堆、字典树）都是为保持这种形状、保证这种速度而专门设计的特殊树。