1.二叉排序树
二叉排序树是一个空树，或者是具有如下性质的二叉树：
- 若它的左子树不为空，则左子树上的所有节点的值均小于它的根节点的值；
- 若它的右子树不为空，则右子树上的所有节点的值均大于它的根节点的值；
- 左右子树都是二叉排序树。
二叉排序树的数据操作效率：
1.查找效率最好为O(log n)、最坏为O(n);
2.插入效率和查找效率相同（先查找插入的位置，且只插入到叶子节点）；
3.删除效率最好为O(log n) + O(1)（只有左或者右子树），最坏为O(log n) + O(log n)（只有左右子树同时存在）
2.平衡二叉树
平衡二叉树是空树或者左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是平衡二叉树。
平衡二叉树牺牲了插入和删除数据的代价，但是提高了查询效率（稳定查询效率为O(log n)）。
3.红黑树
红黑树是一种自平衡二叉排序树，特征如下：
1.节点是红色或者是黑色；
2.根节点是黑色；
3.所有叶子节点都是黑色（叶子节点的值都是NULL）；
4.每个红色节点的两个子节点都是黑色（即从根到叶子遍历不能出现两个连续的红节点）；
5.从任意一个节点到每个叶子节点的所有简单路径都包含相同数据的黑色节点。
红黑树解决的问题，它可以在O(log n)时间复杂度内实现查找，插入和删除，任何不平衡都会在三次旋转内解决。
红黑树.jpg
4.B数（多路查找树）
特征：
1.根节点至少有两个子女节点；
2.每个非根节点包含的关键字个数i满足：n/2 - 1 < i < n -1;
3.除根节点以外的所有节点（不包括叶子节点）的度数正好是关键字的总数+1，故内部子树个数k满足：n/2 < k < n -1;
4.所有的叶子节点都位于同一层。
B树.jpg
5.B+树
B+树是一个n叉树，每个节点通常都有多个孩子，一颗B+树包含根节点、内部节点和叶子节点。B+树的特征如下：
1.有n个子树的节点含有n个关键字；
2.所有叶子节点包含了全部关键字的信息，以及指向这些关键字记录的指针，且叶子节点本身依赖关键字的大小，即自小而大顺序连接；
3.所有的非终端节点可以看成索引的一部分，节点中包含了其他子树的最大或最小关键字。
B+树.jpg
B+树有效内容均保存在叶子节点，且B+树有两个指针，一个指向根节点，一个指向关键字最小的元素的叶子节点，因此B+树支持从根节点开始随机查询和从最小关键字顺序查询。
B+树相比B树拥有更小的磁盘代价，读写代价更低，B+树的查询关键字的路径相等，即从根节点到叶子节点的路径，即每个数据的查询效率相等且稳定。
网友评论