二叉树

发表于 分类于

树是一种分层结构，而层次化这一结构几乎蕴含于所有事物及其联系中，称为其本质属性之一。从文件系统、互联网域名系统，一直到地球生态系统乃至人类社会系统，层次化特征和层次化结构均无所不在。二叉树不再是简单的线性结构，但确定某种次序后具有线性特征，故树属于半线性结构。

树等价于无环联通图，因此与一般的图相同，树也由一组顶点和联接于其间的若干条边组成，故任一节点与根节点之间存在着唯一路径。

二叉树

节点度数不超过2的树称为二叉树，同一节点的孩子和子树，均以左、右区分。

深度为$k$的节点，至多$2^k$个

含$n$个节点的二叉树，高度为$h$的二叉树中，$h<n<2^{h+1}$

1）$n=h+1$时，退化为一条单链

2）$n=2^{h+1}-1$,即所谓的满二叉树

设度数为0，1，2的节点，各有$n_0$,$n_1$,$n_2$个

树为极小联通图，故边数$e=n+1=n_1+2n_2$

叶节点数$n_0=n_2+1$

即$n_1$与$n_0$无关

$h=0$时，$1=0+1$

此后，$n_0$与$n_2$同步递增

特别地，当$n_1=0$时，有$e=2n_2$和$n_0=n_2+1=(n+1)/2$

此时，所有的节点均为偶数，不含单分支节点。

二叉树本身并不具有天然的次序，需要在各个节点与其孩子间定义某种局部次序，从而间接地定义出全局次序。按惯例，左孩子优先于右孩子，将节点和左右孩子分别称为V,L,R,局部次序有VLR,LVR,LRV三种选择，根据节点V的访问次序分别称为先序遍历、中序遍历、后序遍历。

先序遍历

递归版

1
2
3
4
5
6
7
template <typename T, typename VST> //元素类型、操作器
void travPre_R ( BinNodePosi(T) x, VST& visit ) { //二叉树先序遍历算法（递归版）
   if ( !x ) return;
   visit ( x->data );
   travPre_R ( x->lc, visit );
   travPre_R ( x->rc, visit );
}

迭代版

对右子树的递归属于尾递归，左子树的递归接近尾递归，借用尾递归的消除方法，可得到迭代版算法。

1
2
3
4
5
6
7
8
9
template <typename T, typename VST> //元素类型、操作器
void travPre_I1 ( BinNodePosi(T) x, VST& visit ) { //二叉树先序遍历算法（迭代版#1）
   Stack<BinNodePosi(T)> S; //辅助栈
   if ( x ) S.push ( x ); //根节点入栈
   while ( !S.empty() ) { //在栈变空之前反复循环
      x = S.pop(); visit ( x->data ); //弹出并访问当前节点，其非空孩子的入栈次序为先右后左
      if ( HasRChild ( *x ) ) S.push ( x->rc ); if ( HasLChild ( *x ) ) S.push ( x->lc );
   }
}

先序遍历序列可分为两段：

  • 沿最左侧通路自顶而下访问的各节点
  • 自底而上访问遍历的对应右子树

借助栈逆序记录最左侧通路上的节点的右子树，以确定对应右子树自底而上的遍历次序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
template <typename T, typename VST> //元素类型、操作器
void travPre_I2 ( BinNodePosi(T) x, VST& visit ) { //二叉树先序遍历算法（迭代版#2）
   Stack<BinNodePosi(T)> S; //辅助栈
   while ( true ) {
      visitAlongLeftBranch ( x, visit, S ); //从当前节点出发，逐批访问
      if ( S.empty() ) break; //直到栈空
      x = S.pop(); //弹出下一批的起点
   }
}
//从当前节点出发，沿左分支不断深入，直至没有左分支的节点；沿途节点遇到后立即访问
template <typename T, typename VST> //元素类型、操作器
static void visitAlongLeftBranch ( BinNodePosi(T) x, VST& visit, Stack<BinNodePosi(T)>& S ) {
   while ( x ) {
      visit ( x->data ); //访问当前节点
      S.push ( x->rc ); //右孩子入栈暂存（可优化：通过判断，避免空的右孩子入栈）
      x = x->lc;  //沿左分支深入一层
   }
}

中序遍历

递归版

1
2
3
4
5
6
7
template <typename T, typename VST> //元素类型、操作器
void travIn_R ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（递归版）
   if ( !x ) return;
   travIn_R ( x->lc, visit );
   visit ( x->data );
   travIn_R ( x->rc, visit );
}

迭代版

与之前的先序遍历算法不同，沿最左侧分支下行时只是将对应的节点压栈，并没有执行访问操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
template <typename T> //从当前节点出发，沿左分支不断深入，直至没有左分支的节点
static void goAlongLeftBranch ( BinNodePosi(T) x, Stack<BinNodePosi(T)>& S ) {
   while ( x ) { S.push ( x ); x = x->lc; } //当前节点入栈后随即向左侧分支深入，迭代直到无左孩子
}

template <typename T, typename VST> //元素类型、操作器
void travIn_I1 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（迭代版#1）
   Stack<BinNodePosi(T)> S; //辅助栈
   while ( true ) {
      goAlongLeftBranch ( x, S ); //从当前节点出发，逐批入栈
      if ( S.empty() ) break; //直至所有节点处理完毕
      x = S.pop(); visit ( x->data ); //弹出栈顶节点并访问之
      x = x->rc; //转向右子树
   }
}

将上一版等价地描述以下版本：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
template <typename T, typename VST> //元素类型、操作器
void travIn_I2 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（迭代版#2）
   Stack<BinNodePosi(T)> S; //辅助栈
   while ( true )
      if ( x ) {
         S.push ( x ); //根节点进栈
         x = x->lc; //深入遍历左子树
      } else if ( !S.empty() ) {
         x = S.pop(); //尚未访问的最低祖先节点退栈
         visit ( x->data ); //访问该祖先节点
         x = x->rc; //遍历祖先的右子树
      } else
         break; //遍历完成
}

以上版需借助辅助栈，所需辅助空间正比于二叉树的高度，在最坏情况下与节点数目相当。借助BinNode对象内部的parent指针，以下版本仅需要常数辅助空间，属于就地算法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
template <typename T, typename VST> //元素类型、操作器
void travIn_I3 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（迭代版#3，无需辅助栈）
   bool backtrack = false; //前一步是否刚从右子树回溯——省去栈，仅O(1)辅助空间
   while ( true )
      if ( !backtrack && HasLChild ( *x ) ) //若有左子树且不是刚刚回溯，则
         x = x->lc; //深入遍历左子树
      else { //否则——无左子树或刚刚回溯（相当于无左子树）
         visit ( x->data ); //访问该节点
         if ( HasRChild ( *x ) ) { //若其右子树非空，则
            x = x->rc; //深入右子树继续遍历
            backtrack = false; //并关闭回溯标志
         } else { //若右子树空，则
            if ( ! ( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
            backtrack = true; //并设置回溯标志
         }
      }
}
template <typename T> BinNodePosi(T) BinNode<T>::succ() { //定位节点v的直接后继
   BinNodePosi(T) s = this; //记录后继的临时变量
   if ( rc ) { //若有右孩子，则直接后继必在右子树中，具体地就是
      s = rc; //右子树中
      while ( HasLChild ( *s ) ) s = s->lc; //最靠左（最小）的节点
   } else { //否则，直接后继应是“将当前节点包含于其左子树中的最低祖先”，具体地就是
      while ( IsRChild ( *s ) ) s = s->parent; //逆向地沿右向分支，不断朝左上方移动
      s = s->parent; //最后再朝右上方移动一步，即抵达直接后继（如果存在）
   }
   return s;
}

此版相当于将原辅助栈替换为一个标志位backtrack，标志是否有从下而上的回溯。若不是，则按照中序遍历的策略优先遍历左子树，否则，则意味着当前左子树已访问完毕，访问当前节点后深入右子树。

改进该算法，无需辅助栈，也无需辅助标志位。

1
2
3
4
5
6
7
8
9
10
11
12
13
template <typename T, typename VST> //元素类型、操作器
void travIn_I4 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历（迭代版#4，无需栈或标志位）
   while ( true )
      if ( HasLChild ( *x ) ) //若有左子树，则
         x = x->lc; //深入遍历左子树
      else { //否则
         visit ( x->data ); //访问当前节点，并
         while ( !HasRChild ( *x ) ) //不断地在无右分支处
            if ( ! ( x = x->succ() ) ) return; //回溯至直接后继（在没有后继的末节点处，直接退出）
            else visit ( x->data ); //访问新的当前节点
         x = x->rc; //（直至有右分支处）转向非空的右子树
      }
}

无论二叉树的规模如何，对succ()接口所有调用所需时间总和不超过O(n)

在这一场合对succ的调用，其中if判断语句必然取else分支，因此，算法所消耗的所有时间应线性正比于其中while循环的部署，即其中对parent引用的访问次数。数学归纳法对树高归纳可证明对parent引用不超过$n$次。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
template <typename T, typename VST> //元素类型、操作器
void travIn_I3 ( BinNodePosi(T) x, VST& visit ) { //二叉树中序遍历算法（迭代版#3，无需辅助栈）
   bool backtrack = false; //前一步是否刚从右子树回溯——省去栈，仅O(1)辅助空间
   while ( true )
      if ( !backtrack && HasLChild ( *x ) ) //若有左子树且不是刚刚回溯，则
         x = x->lc; //深入遍历左子树
      else { //否则——无左子树或刚刚回溯（相当于无左子树）
         visit ( x->data ); //访问该节点
         if ( HasRChild ( *x ) ) { //若其右子树非空，则
            x = x->rc; //深入右子树继续遍历
            backtrack = false; //并关闭回溯标志
         } else { //若右子树空，则
            if ( ! ( x = x->succ() ) ) break; //回溯（含抵达末节点时的退出返回）
            backtrack = true; //并设置回溯标志
         }
      }
}

每个节点都仅在左子树被访问完成后接受访问，所以只访问一次。

另外，此处并未显式地使用复杂的辅助结构，表面上看只需要常数辅助空间，但是相比于其余算法，该算法要求每个算法均有parent指针，仍为$O(n)$空间。

后序遍历

递归版

1
2
3
4
5
6
7
template <typename T, typename VST> //元素类型、操作器
void travPost_R ( BinNodePosi(T) x, VST& visit ) { //二叉树后序遍历算法（递归版）
   if ( !x ) return;
   travPost_R ( x->lc, visit );
   travPost_R ( x->rc, visit );
   visit ( x->data );
}

迭代版

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
template <typename T> //在以S栈顶节点为根的子树中，找到最高左侧可见叶节点
static void gotoHLVFL ( Stack<BinNodePosi(T)>& S ) { //沿途所遇节点依次入栈
   while ( BinNodePosi(T) x = S.top() ) //自顶而下，反复检查当前节点（即栈顶）
      if ( HasLChild ( *x ) ) { //尽可能向左
         if ( HasRChild ( *x ) ) S.push ( x->rc ); //若有右孩子，优先入栈
         S.push ( x->lc ); //然后才转至左孩子
      } else //实不得已
         S.push ( x->rc ); //才向右
   S.pop(); //返回之前，弹出栈顶的空节点
}

template <typename T, typename VST>
void travPost_I ( BinNodePosi(T) x, VST& visit ) { //二叉树的后序遍历（迭代版）
   Stack<BinNodePosi(T)> S; //辅助栈
   if ( x ) S.push ( x ); //根节点入栈
   while ( !S.empty() ) {
      if ( S.top() != x->parent ) //若栈顶非当前节点之父（则必为其右兄），此时需
         gotoHLVFL ( S ); //在以其右兄为根之子树中，找到HLVFL（相当于递归深入其中）
      x = S.pop(); visit ( x->data ); //弹出栈顶（即前一节点之后继），并访问之
   }
}

在后续遍历序列中，栈顶元素应后于栈顶子树访问，所以后序遍历序列并不是访问栈顶元素，而是先判断对应子树是否遍历，若遍历再访问栈顶元素。

在迭代版后序遍历算法运行中，树中每一层至多有两个节点存在栈中，故栈结构最大规模不超过二叉树深度的两倍，最坏情况下为$O(n)$。

层次遍历

递归的形式类似于栈，层次遍历的顺序与栈访问顺序有所不同，所以借助与栈对称的队列结构实现层次遍历。

1
2
3
4
5
6
7
8
9
10
template <typename T> template <typename VST> //元素类型、操作器
void BinNode<T>::travLevel ( VST& visit ) { //二叉树层次遍历算法
   Queue<BinNodePosi(T)> Q; //辅助队列
   Q.enqueue ( this ); //根节点入队
   while ( !Q.empty() ) { //在队列再次变空之前，反复迭代
      BinNodePosi(T) x = Q.dequeue(); visit ( x->data ); //取出队首节点并访问之
      if ( HasLChild ( *x ) ) Q.enqueue ( x->lc ); //左孩子入队
      if ( HasRChild ( *x ) ) Q.enqueue ( x->rc ); //右孩子入队
   }
}

队列中所存节点的深度不超过1，故最大规模不超过二叉树任一的相邻两层的规模之和。

只要辅助队列Q的容量不低于$\lceil n/2 \rceil$ ,就不会出现中途溢出的问题

在算法的每一步迭代过程中，若当前至少有$n$各个元素入过队，则在队中的至多$\lceil n/2 \rceil$,相应地，至少有$\lfloor n/2 \rfloor$个已经出队。每次迭代都会有一个节点出队，若该节点的度数为$d(0<=d<=2)$，则随即会有$d$个节点入队，通过对已出队的节点做数学归纳可证。

在算法的任一时刻，辅助队列的规模均不至小于仍在队列中节点的数目。为了使仍在队列中节点数目占当前入过队节点比重尽可能大，此前所有出队节点度数都必须取作最大的2，且中途一旦某个节点只有1度甚至0度，则不可能恢复到这一比重，即当树为规模为n的完全二叉树时需要如此大容量的队列。

在整个遍历过程中，规模为$n$的完全二叉树为单峰对称的，即

1
2
{0,1,2,..(n+1)/2,...,2,1,0}
{0,1,2,..n/2,n/2,...,2,1,0}

$n$为偶数时，最后一个内部节点度数为1，入一出一，所以队列规模不变。

完全二叉树

叶节点仅限于最低两层

底层叶子均居于次底层叶子左侧，除末节点的父亲，内部节点均有叶子。

叶节点不致少于内部节点，但至多多出一个。

分为两种情况：

  • 各节点均为二度节点 $n_0=n_1+n_2+1=n_2+1$
  • 有一节点为一度 $n_0=n_2+1=n_2+n_1$

这些算法的确会访问每个节点一次且仅一次

只要某个节点可以被访问到，则其孩子节点必然也能

由此进一步可知：只要某个节点能被访问到，则其每个后代节点必然也能。于是特别地，作为根节点地后代，树中所有节点都能被起始于根节点的遍历访问到。

另外一方面，任何节点仅被访问一次。

除了层次遍历算法和中序遍历算法均借助辅助栈进行访问，注意到每个节点都在且仅在刚刚出栈后，随即被访问。每个节点各自仅入栈一次，即可确定每个节点的确至多被访问一次。

层次遍历算法和中序遍历算法未使用到栈结构，性质类似。

这些算法都具有线性时间复杂度

这些算法的运行时间主要消耗于两个部分：

  • 栈(队列)操作
  • 对节点的访问操作

以上操作对每个节点而言均为常数次，所以总体而言，这些算法具有线性时间复杂度。

递推方程分析

$T(n)=T(n-a-1)+T(a)+O(1)$

每递归一层，等效于将当前问题分解为两个子问题，递归基只需常数时间，同样可以得出这些算法具有线性复杂度的结论。

二叉编码树

通讯理论中一个基本的问题是：如何在尽可能低的成本的情况下，以尽可能高的速度，尽可能忠实地实现信息在空间和时间上的复制和转移。在现代通讯技术中，无论采用电、磁、光、电或其他任何形式，在信道上传递的信息大多以二进制比特的形式表示和存在，而每一个具体的编码方案都对应于一棵二叉编码树。

在加载到信道上之前，信息被转换为二进制的过程被称为编码，反之，信道抵达目标后再由二进制编码回复原始信息的过程被称为解码。

任一编码方案都可描述为一棵二叉树：从根节点出发，每次向左(右)对应一个0(1)比特位。各字符分别存放于对应的叶子中。字符x的编码串rps(v(x))=rps(x)由根到v(x)的通路确定。

字符编码不必等长，所有字符都对应于叶节点，不存在解码歧义现象，为前缀无歧义编码，不同字符的编码互不为前缀，故不致歧义，此为可行的PFC编码方案。

若采用PFC编码，则无论二进制编码串的长度与内容如何，解码过程总能持续进行

整个解码过程就是在PFC编码树上的下行过程，从根节点出发，根据编码串的当前编码相应地向左(比特0)或向右(比特1)深入，一旦抵达叶节点，则输出其对应的字符，并随即复位至根节点。

可见，算法无法继续的唯一可能情况为，在准备向下深入时没有发现对应的分支，然而根据定义和约束条件，PFC编码树必然是真二叉树，每一内部节点必然拥有左、右分支，因此上述情况不可能发生。

解码过程不必回溯，若因为信道干扰等因素导致某个比特位翻转错误，尽管解码依然可进行，但是后续所有字符的解码都会出现错误。

最优编码树

在实际的通讯系统中，信道的使用效率很大程度上取决于编码本身的效率。比如，高效的算法生成的编码串应尽可能短。

字符x的编码长度|rps(x)|为其对应叶节点的深度depth(v(x))。于是，各字符的平均编码长度就是编码树T中的叶节点平均深度。

$ald(T)=\sum_{x\in \sum}|rps(x)|/|\sum|=\sum_{x\in \sum}depth(x)/|\sum|$

平均编码长度是反应编码效率的重要指标，我们尽可能希望这一指标小。同一字符集的所有编码方案中，平均编码长度最小者被称为最优方案，对应编码树的ald()值达到最小，故称之为最优编码树，简称最优编码树。对于任一字符集，最优编码树必然存在。

双子性

最优编码树必然为真二叉树，内部节点的左、右孩子全双，不然，假设其中内部节点p有唯一的孩子x，则将p删除并代之以子树x。除了子树中所有叶节点的编码长度统一缩短一层外，其余叶节点的编码长度不变，相比于之前的编码树平均编码长度必然更短。

层次性

叶节点位置深度之差不超过1，类似双子性的证明，替换后可得到的编码树平均编码长度更短，不符合最优编码树的原则。

不唯一性

对于任一内部节点而言，左右子树互换之后平均编码长度不变。

最优编码树的构造

真完全树为最优编码树，可直接导出构造最优编码树的算法：创建一棵规模为$2|\sum|-1$的完全二叉树T，将$\sum$中的字符任意分配给T的$|\sum|$个节点。

若不同序列作为输出的概率均等，则任何CBA式排序算法平均运行时间仍然为$\Omega(nlogn)$

针对CBA式算法复杂度的下界估计，统一方法为：

  • 确定算法所对应的比较树
  • 通过输入规模与可能的输出结果(叶节点)数目推算出最小树高

在各种输出结果符合某种概率分布的情况下，算法的平均性能，则等效于比较树中各叶节点的加权平均深度。

最优编码树在各种输出结果均等的情况下，对于任一固定输入规模n，完全二叉树的叶节点平均深度可达到最小。

huffman编码树

以上最优编码树算法假定各个字符在文本串中出现的次数相等，而这一条件往往不满足，甚至不确定。

若考虑字符各自出现频率，则可将带权平均编码长度取作编码树T的叶节点带权平均深度，即是

$wald(T)=\sum_{x\in \sum}p(x)|rps(x)|$

此时，完全二叉编码树并不是wald值最短。

最优带权编码树

频率高的超字符，应尽可能放在高/低处。

同样，huffman编码树满足层次性、双子性、不唯一性。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
HuffTree* minHChar ( HuffForest* forest ) { //在Huffman森林中找出权重最小的（超）字符
   ListNodePosi ( HuffTree* ) p = forest->first(); //从首节点出发查找
   ListNodePosi ( HuffTree* ) minChar = p; //最小Huffman树所在的节点位置
   int minWeight = p->data->root()->data.weight; //目前的最小权重
   while ( forest->valid ( p = p->succ ) ) //遍历所有节点
      if ( minWeight > p->data->root()->data.weight ) //若当前节点所含树更小，则
         {  minWeight = p->data->root()->data.weight; minChar = p;  } //更新记录
   return forest->remove ( minChar ); //将挑选出的Huffman树从森林中摘除，并返回
}

HuffTree* generateTree ( HuffForest* forest ) { //Huffman编码算法
   while ( 1 < forest->size() ) {
      HuffTree* T1 = minHChar ( forest ); HuffTree* T2 = minHChar ( forest );
      HuffTree* S = new HuffTree(); 
      S->insertAsRoot ( HuffChar ( '^', T1->root()->data.weight + T2->root()->data.weight ) );
      S->attachAsLC ( S->root(), T1 ); S->attachAsRC ( S->root(), T2 );
      forest->insertAsLast ( S ); 
   } //assert: 循环结束时，森林中唯一（列表首节点中）的那棵树即Huffman编码树
   return forest->first()->data;
}
static void //通过遍历获取各字符的编码
generateCT ( Bitmap* code, int length, HuffTable* table, BinNodePosi ( HuffChar ) v ) {
   if ( IsLeaf ( *v ) ) //若是叶节点（还有多种方法可以判断）
      {  table->put ( v->data.ch, code->bits2string ( length ) ); return;  }
   if ( HasLChild ( *v ) ) //Left = 0
      { code->clear ( length ); generateCT ( code, length + 1, table, v->lc ); }
   if ( HasRChild ( *v ) ) //Right = 1
      { code->set ( length ); generateCT ( code, length + 1, table, v->rc ); }
}

HuffTable* generateTable ( HuffTree* tree ) { //将各字符编码统一存入以散列表实现的编码表中
   HuffTable* table = new HuffTable; Bitmap* code = new Bitmap;
   generateCT ( code, 0, table, tree->root() ); release ( code ); return table;
};

每迭代一次，森林的规模减1,故共需迭代n-1此，直到只剩一棵树。minHChar() 每次都要遍历森林中所有的超字符，所需时间线性正比于当时森林的规模。因此总体运行时间应为：

$O(1)+O(n-1)+…+O(2)=O(n^2)$

任何CBA式huffman树构造算法在最坏情况下都需要运行$\Omega(nlog n)$时间

只需建立一个从排序问题到huffman编码树问题的线性归约

事实上，对于每一个待排序的输入序列，我们都将其视为一组字符的出现频率。不失一般性，假设每个元素非负，否则可在$O(n)$时间内令它们增加同一足够大的正数。

以这组频率作为输入，可以调用任何CBA式算法构造出huffman编码树，一旦得到这样一棵编码树，只需一趟层次遍历，即可在$O(n)$时间内得到所有叶节点的遍历序列。

根据huffman编码树的定义，该树必然是单调的。因此，整个过程也等效于同时完成了对原输入序列的排序。

若待编码字符集已按出现频率排序，则huffman编码可以更快完成。始终将森林中的树分为两类：单节点(尚未参与合并)和多节点(已合并过)。每经过一次迭代，后者虽不见得增多，但必然有一个新成员。

根据huffman编码树的原理，每次迭代都是在当前森林中选取权重最小的两棵树合并，因此，被选出的树权重必然单调非降，故在当前所有(经合成生成后)多节点树中，最新者的权重必然最大。

将以上两类节点组织为两个队列，初始状态下，所有字符按照权重非降的次序存入单节点的队列，而多节点的队列，直接置空。此后的过程与常规的huffman编码树类似，反复取出权重最小的两棵树，将其合并后插回森林，直至最后只剩下一棵树

键树

关联数组（Associative Array），又称映射（Map）、字典（Dictionary）是一个抽象的数据结构、，它包含着类似于（键，值）的有序对。一个关联数组中的有序对可以重复（如C++中的multimap）也可以不重复（如C++中的map)。

Trie在计算机科学中又称前缀树和键树，是一种保存关联数组的有序树，其中的键通常是字符串。与二叉查找树不同，键不是直接保存在节点中，而是由节点在树中的位置决定。一个节点的所有子孙都有相同的前缀，也就是这个节点对应的字符串，而根节点对应空字符串。一般情况下，不是所有的节点都有对应的值，只有叶子节点和部分内部节点所对应的键才有相关的值。

Trie这个术语来自于retrieval，trie树常用于搜索提示。如当输入一个网址，可以自动搜索出可能的选择。当没有完全匹配的搜索结果，可以返回前缀最相似的可能。

任一字符串集s都可表示为一棵键树。键树是有根有序树，其中每个节点均有r个分支，深度为d的节点对应于长度为d的字符串，祖先对应的字符串必定为后代所对应字符串的前缀。键树只保留与S中字符串相对应的节点，其余分支均标记为null。

因为并不确保字符串相互不为前缀，所以对应于完整字符串的节点未必是叶子，每个非空指针通过标志位来表明是否表示s中某个完整的字符串。

基于键树实现词典的get(),put(),remove()接口时间复杂度分别为$O(h)$,$O(hr)$,$O(hr)$。

若以向量实现键树，则put(),remove()复杂度中的因子r不可消除

在最坏情况下，在创建每个节点后，都需要花费$O(r)$时间，将对应向量中的每个指针都初始化为NULL。

同样，在最坏情况下，在删除每个节点后，都需要花费$O(r)$时间确认对应向量是否都是NULL。

以上方式在最坏情况下需要$\Omega(nr)$空间，其中$n=|s|$为字符串的规模。若s中的字符串均互不为前缀，则每个字符串都将对应于一个叶节点。于是，即便只计入这$n$个叶节点，累计空间总量为$\Omega(nr)$。

若用链表来实现各节点，每个节点的规模与实际的分支数成正比，每个字符串的每个字符至多占用$O(1)$空间，故所需空间总量线性正比于S中所有字符串的长度总和，同时，在每个节点需要$O( r )$时间顺序查找以确定深入的分支方向。get()接口的效率将降至$O(hr)$,其中h为树高，同时也是S中字符串的最大长度。

基数树

键树中往往包含大量的单分支节点，通过折叠合并相邻的单分支节点，进一步提高键树的效率。

基数树，或称Patricia trie/tree，或crit bit tree，压缩前缀树，是一种更节省空间的Trie（前缀树）。对于基数树的每个节点，如果该节点是唯一的子树的话，就和父节点合并。一棵Patricia Trie的任何内部结点有2个或以上的孩子结点。

将向量地单分支节点合成一个大节点，尽管一定程度上可以提高时、空效率，但是在渐进意义上并无实质改进。

应用：

三叉树

Trie树结构，它的实现简单但空间效率低。如果要支持26个英文字母，每个节点就要保存26个指针，假若我们还要支持国际字符、标点符号、区分大小写，内存用量就会急剧上升，以至于不可行。

类似于二叉查找树，三叉查找树(ternarry tree)可以用于实现带前缀搜索功能的关联数组。比标准的前缀树更省空间，但是查找速度有所下降。