一、树的概念

1、树是 n(n 多 0)个结点的有限集合,一棵树满足以下两个条件:
(1)当 n=0 时,称为空树;
(2)当 n>0 时,有且仅有一个称为根的结点,除根结点外,真余结点分 m(m≥0)个互不
相交的非空集合 T 1 ,T 2 ,…,T m ,这些集合中的每一个都是一棵树,称为根的子树。
2、森林(Forest)是 m(m>0)棵互不相交的树的集合。树的每个结点的子树是森林。删除一个非空树的根结点,它的子树便构成森林。

二、树的相关术语

(1) 结点的度:树上任一结点所拥有的子树的数目称为该结点的度。
(2) 叶子:度为 0 的结点称为叶子或终端结点。
(3) 树的度:一棵树中所有结点的度的最大值称为该树的度。
(4) 一个结点的子树的根称为该结点的孩子(或称子结点)。相应地该结点称为孩子的双亲(也称父结点)。
(5) 结点的层次:从根开始算起,根的层次为 1,其余结点的层次为其双亲的层次加 1。
(6) 树的高度:一棵树中所有结点层次数的最大值称为该树的高度或深度。
(7) 有序树:若树中各结点的子树从左到右是有次序的,不能互换,称为有序树。有序树中最左边子树的根称为第 1 个孩子,左边第 i 个子树的根称为第 i 个孩子。
(8) 无序树:若树中各结点的子树是无次序的,可以互换,则称为无序树。

三、树的遍历

树的遍历:
(1)先序遍历
(2)后序遍历
(3)层次遍历。

四、树的链表存储结构

1.双亲表示法：
双亲表示法由一个一维数组构成。数组的每个分量包含两个域:数据域和双亲域。数据域用于存储树上一个结点中数据元素,双亲域用于存储本结点的双亲结点在数组中的序号(下标值)。

2.孩子链表表示法
带双亲的孩子链表表示法
3.孩子兄弟链表表示法
存储时每个结点除了数据域外,还有指向该结点的第一个孩子和下一个兄弟结点的指针。

五、时间复杂度

时间频度

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。

时间复杂度

在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。 一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

六、B+树及B树的区别

B+树索引是B+树在数据库中的一种实现，是最常见也是数据库中使用最为频繁的一种索引。B+树中的B代表平衡（balance），而不是二叉（binary），因为B+树是从最早的平衡二叉树演化而来的。
结构上：
1、B树中关键字集合分布在整棵树中，叶节点中不包含任何关键字信息，而B+树关键字集合分布在叶子结点中，非叶节点（内节点）只是叶子结点中关键字的索引（键值）；
2、B树中任何一个关键字只出现在一个结点中，而B+树中的关键字必须出现在叶节点中，也可能在非叶结点中重复出现；
3、B树中所有键值只存储一份，而B+树中，除去叶子节点存储所有数据外，还有只存储键值数据的非叶子节点（内节点）。因此，B+树比B树更占用空间，但B+树以空间为代价换取到了性能的提升。
4、从树的高度来看，B树索引的关键字数据分布在整棵树中向下拉伸，因此B树的深度相对较高，深度越高，查询、修改和维护的成本都会增加。而B+树中‘索引节点’（非叶子节点）对应叶子节点，横向扩展的特点使得B+树的时间复杂度是固定的。

性能上：
不同于B树只适合随机检索，B+树同时支持随机检索和顺序检索；
1、B+树的磁盘读写代价更低。B+树的内部结点并没有指向关键字具体信息的指针，其内部结点比B树小，盘块能容纳的结点中关键字数量更多，一次性读入内存中可以查找的关键字也就越多，相对的，IO读写次数也就降低了。而IO读写次数是影响索引检索效率的最大因素。
2、B+树的查询效率更加稳定。B树搜索有可能会在非叶子结点结束，越靠近根节点的记录查找时间越短，只要找到关键字即可确定记录的存在，其性能等价于在关键字全集内做一次二分查找。而在B+树中，顺序检索比较明显，随机检索时，任何关键字的查找都必须走一条从根节点到叶节点的路，所有关键字的查找路径长度相同，导致每一个关键字的查询效率相当。
B树在提高了磁盘IO性能的同时并没有解决元素遍历的效率低下的问题。B+树的叶子节点使用指针顺序连接在一起，只要遍历叶子节点就可以实现整棵树的遍历。而且在数据库中基于范围的查询是非常频繁的，而B树不支持这样的操作（或者说效率太低）。