二叉查找树、AVL树、红黑树、B树和B+树
二叉查找树(BST)
二叉查找树也称为二叉查找树,具有以下性质:
- 若左子树不为空,则左子树的值均小于根节点的值。
- 若右子树不为空,则右子树的值均大于根节点的值。
- 左、右子树也分别是二叉查找树。
AVL树
平衡二叉树(AVL Tree)在符合二叉查找树的条件下,还满足任何节点的两个子树的高度差最大为1。
红黑树
红黑树是一种二叉查找树,但在每个节点增加一个存储位表示节点的颜色,可以是red或black。通过对任何一条从根到叶子的路径上各个节点着色的方式的限制,红黑树确保没有一条路径会比其他路径长出两倍,它是一种弱平衡二叉树(由于是弱平衡,可以推出,相同的情况下,AVL树的高度低于红黑树),相对于要求严格的AVL树来说,它的旋转次数变少,所以对于搜索,插入,删除操作多的情况下,就使用红黑树。
具有以下性质:
- 每个节点非红即黑。
- 根节点是黑的。
- 每个叶节点(叶节点即树尾端null指针或null节点)都是黑的。
- 如果一个节点是红的,那么它的两个儿子都是黑的。
- 对于任意节点而言,其到叶子点树NIL指针的每天路径都包含相同的黑节点。
B/B+树
B/B+树是为磁盘或其它存储设备而设计的一种平衡多路查找树(相对于二叉,B树每个内节点有多个分支),与红黑树相比,在相同的节点的情况下,一棵B/B+树的高度远远小于红黑树的高度。B/B+树上操作的时间通常由存储磁盘的时间和CPU计算时间这两个部分构成,而CPU的速度非常快,所以B树的操作效率取决于访问磁盘的次数,关键字总数相同的情况下B树的高度越小,磁盘I/O所花的时间越少。
B树的性质:
定义任意非叶子结点最多只有M个儿子,且M>2;
根结点的儿子数为[2,M];
除根结点以外的非叶子节点的儿子数为[M/2,M];
每个节点存放至少M/2-1(取上整)和至多M-1个关键字;(至少两个关键字)
非叶子结点的关键字个数=指向儿子的指针个数-1;
非叶子结点的关键字:K[1], K[2], …, K[M-1];且K[i] < K[i+1];
非叶子结点的指针:P[1], P[2], …, P[M];其中P[1]指向关键字小于K[1]的子树,P[M]指向关键字大于K[M-1]的子树,其它P[i]指向关键字属于(K[i-1], K[i])的子树;
所有叶子结点位于同一层;
B+树是应文件系统所需而产生的一种B树的变形树(文件的目录一级一级索引,只有最底层的叶子节点(文件)保存数据),非叶子节点只保存索引,不保存实际的数据,数据都保存在叶子节点中。所有的非叶子节点都可以看成索引部分。
B+树的性质:
非叶子节点的子树指针与关键字个数相同;
非叶子节点的子树指针p[i],指向关键字值属于[k[i],k[i+1]]。(B树是开区间,也就是说B树不允许关键字重复,B+树允许重复)
为所有叶子节点增加一个链指针。
所有关键字都在叶子节点出现(稠密索引)。(且链表中的恰是有序的);
非叶子节点相当于叶子节点的索引(稀疏索引),叶子节点相当于是存储(关键字)数据的数据层。