数据结构——二叉搜索树、B树、B-树

数据结构——二叉搜索树、B树、B-树

1. 综述

　　二叉排序树(Binary Sort Tree)，又叫二叉查找树(Binary Search Tree)，也叫二叉排序树。

　　二叉搜索树满足以下性质：

　　1. 若根结点左子树不为空，则左子树上的所有结点均小于根结点；

　　2. 若根结点右子树不为空，则右子树上的所有结点均大于根结点；

　　3. 其左右子树也是二叉搜索树(递归定义)；

　　4. 没有键值相等的点。

　　平衡二叉树(Balanced Binary Tree)，是二叉查找树的一个进化体，引入了平衡的概念；以两位发现者命名，又叫AVL树。博客链接：平衡二叉树

　　B树就是B-树。B树/B-树英文叫B-Tree，可能被不小心翻译成了B-树。B-树是一种多路的平衡查找树。博客链接：B树的介绍

　　B树适当增加了结点中关键字的个数，每个结点都被保存在一个页中，受页大小的限制，每个结点中子树的个数(关键字的个数 + 1)不能超过某个最大值；为充分利用空间，每个结点中子树的个数也不能小于最大值的一半，因为有两个这样的结点就可以合成一个结点；根结点中至少有两个关键字，可以少于最大值的一半，如果只有一个子树个数小于最大值一半的结点，那它就是根结点。

　　所以就有了B树/B-树需满足的条件(书中定义)，对于m阶B-树：

　　1. 树中每个结点最多有m棵子树；

　　2. 若根结点不是叶子结点，则至少有两棵子树；

　　3. 除了根结点，其他所有非终端结点至少有⌈m/2⌉棵子树；

　　4. 每个非终端结点包含关键字和指向字数的指针：(n, A0, K1, A1, …… , Kn, An), n为关键字个数，子树数为n+1；

　　5. 所有叶子结点都在同一层，且不带信息。

　　个人理解：由第4点计算的结点大小为2n+2，也就是跟n+1成正比，也就是跟结点的子树数成正比。所以定义中都用子树数来描述，而不是用关键字个数。

　　其实每个结点应该还包含指向每个关键字对应记录的指针，这样算来结点大小为3n+2，不跟结点的子树数成正比。或许是这一点差异被忽略了，或者还有我不知道的情况。