数据结构中为了存储和查找的方便，用各种树结构来存储文件，此文就简单总结一下各种树的特点，使读者对常见的树有个基本的认识，针对不同树的详解有专门的文章描述。本章涉及的树结构包括：二叉查找树（二叉排序树）、平衡二叉树（AVL树）、红黑树、B-树、B+树、B*树、(字典树（trie树）、后缀树、广义后缀树，这些不做讲解)。

1、二叉查找树（二叉排序树/BST树）

（图a）

二叉查找树是一种动态查找表（图a），具有这些性质：

（1）所有非叶子结点至多拥有两个儿子（Left和Right）

（2）所有结点存储一个关键字

（3）若它的左子树不为空，则左子树上的所有节点的值都小于它的根节点的值；

（4）若它的右子树不为空，则右子树上所有节点的值都大于它的根节点的值；

（5）其他的左右子树也分别为二叉查找树；

（6）二叉查找树是动态查找表，在查找的过程中可见添加和删除相应的元素，在这些操作中需要保持二叉查找树的以上性质。

【说明】

        如果BST树的所有非叶子结点的左右子树的结点数目均保持差不多（平衡），那么B树

的搜索性能逼近二分查找；但它比连续内存空间的二分查找的优点是，改变BST树结构

（插入与删除结点）不需要移动大段的内存数据，甚至通常是常数开销；

       如：

   但BST树在经过多次插入与删除后，有可能导致不同的结构：

右边也是一个BST树，但它的搜索性能已经是线性的了；同样的关键字集合有可能导致不同的

树结构索引；所以，使用BST树还要考虑尽可能让BST树保持左图的结构，和避免右图的结构，也就

是所谓的“平衡”问题。

2、平衡二叉树（AVL树）

含有相同节点的二叉查找树可以有不同的形态，而二叉查找树的平均查找长度与树的深度有关，所以需要找出一个查找平均长度最小的一棵，那就是平衡二叉树（图b），具有以下性质：

（图b）

（1）要么是棵空树，要么其根节点左右子树的深度之差的绝对值不超过1；

（2）其左右子树也都是平衡二叉树；

（3）二叉树节点的平衡因子定义为该节点的左子树的深度减去右子树的深度。则平衡二叉树的所有节点的平衡因子只可能是-1,0,1。

3、红黑树

（图c）

红黑树是一种自平衡二叉树，在平衡二叉树的基础上每个节点又增加了一个颜色的属性，节点的颜色只能是红色或黑色。具有以下性质：

（1）根节点只能是黑色；

（2）每个结点要么是红的，要么是黑的；

（3）每个叶结点，即空结点（NIL）是黑的；

（4）对每个结点，从该结点到根结点的所有路径上包含相同数目的黑结点。

4、B-树

  如：（M=3）

（图d）

B-树是一种平衡多路查找树，它在文件系统中很有用。一棵M阶B-树（图d为3阶B-树），具有下列性质：

（1）树中每个节点至多有M棵子树；

（2）若根节点不是叶子节点，则子树个数的范围为[2, M]；

（3）除根结点以外的非叶子结点的子树个数的范围为[M/2, M]；

（4）每个结点存放至少M/2-1（取上整）和至多M-1个关键字，（至少2个关键字）；

（5）所有的叶子节点都出现在同一层次上，且不带任何信息，也是为了保持算法的一致性。

5、B+树

    如：（M=3）

（图e）

B+数是B-树的一种变形，它与B-树的差别在于（图e为3阶B+树）：

（1）有n棵子树的节点含有n个关键字；

（2）所有的叶子节点包含了全部关键字的信息，及指向这些关键字记录的指针，且叶子节点本身按关键字大小自小到大顺序链接；

（3）所有非终端节点可以看成是索引部分，节点中仅含有其子树（根节点）中最大（或最小）关键字，所有B+树更像一个索引顺序表；

（4）对B+树进行查找运算，一是从最小关键字起进行顺序查找，二是从根节点开始，进行随机查找。

【说明】

更适合文件索引系统；比如对已经建立索引的数据库记录，查找10<=id<=20，那么只要通过根节点搜索到id=10的叶节点，之后只要根据叶节点的链表找到第一个大于20的就行了，比B-树在查找10到20内的每一个是每次都从根节点出发查找提高了不少效率。

6、B*树

是B+树的变体，在B+树的非根和非叶子结点再增加指向兄弟的指针：

（图f）

（1）B*树定义了非叶子结点关键字个数至少为(2/3)*M，即块的最低使用率为2/3

（代替B+树的1/2）；

（2）B+树的分裂：当一个结点满时，分配一个新的结点，并将原结点中1/2的数据复制到新结点，最后在父结点中增加新结点的指针；B+树的分裂只影响原结点和父结点，而不会影响兄弟结点，所以它不需要指向兄弟的指针；

B*树的分裂：当一个结点满时，如果它的下一个兄弟结点未满，那么将一部分数据移到兄弟结点中，再在原结点插入关键字，最后修改父结点中兄弟结点的关键字（因为兄弟结点的关键字范围改变了）；如果兄弟也满了，则在原结点与兄弟结点之间增加新结点，并各复制1/3的数据到新结点，最后在父结点增加新结点的指针；

所以，B*树分配新结点的概率比B+树要低，空间使用率更高；

【B树相关的小结】

       B树：二叉树，每个结点只存储一个关键字，等于则命中，小于走左结点，大于走右结点；

       B-树：多路搜索树，每个结点存储M/2到M个关键字，非叶子结点存储指向关键字范围的子结点；所有关键字在整颗树中出现，且只出现一次，非叶子结点可以命中；

       B+树：在B-树基础上，为叶子结点增加链表指针，所有关键字都在叶子结点中出现，非叶子结点作为叶子结点的索引；B+树总是到叶子结点才命中；

       B*树：在B+树基础上，为非叶子结点也增加链表指针，将结点的最低利用率从1/2提高到2/3；