2-3查找树(2-3 search trees)

前言：

前面我们学习了基本的二叉树，现在我们来学习另一种效率更高的树——平衡查找树，这种树有几种：

AVL

2-3 Search Trees

Red-black BSTs ——红黑二叉查找树
今天我们先从最简单的学习：2-3 查找树

2-3 查找树：

2-3查找树与二叉树有两个十分明显的区别：

1. 二叉树中子节点都比父节点要大或要小，二者取其一。而2-3 查找树中左子节点的值小于父节点，右子节点的值大于父节点的值。

2. 二叉树中各节点只有一个值，而2-3 查找树中有两种节点。

       2-节点: 一个值，两个子节点

       3-节点：两个值，三个子节点

下面来看看2-3 查找树的基本操作：

search操作：

insert操作：

1. 对于2-节点的插入：

2. 对于3-节点的插入：

（1）要插入的地方只有单个3-节点：

（2）要插入的3-节点的父节点是2-节点

（3）要插入3-节点的父节点是3-节点

还有一种情况就是在插入后不断分裂，不断往上传递，一直到根节点，刚好根节点也是3-节点，那就根节点也分裂。

总结：

2-3查找树效率很高，其时间复杂度：

最坏的情况: log2 N. [all 2-nodes] 

最好的情况: log3 N ≈ 0.631 lg N. [all 3-nodes] 

 

 

最后强烈推荐Coursera上普林斯顿大学的算法课点击打开链接

 

 

以上内容纯属个人学习总结，不代表任何团体或单位。若有理解不到之处请见谅！