在查找操作中,经常会用到二叉查找树,其最好的性能是O(logN),但是,由于输入的不同,所以一个查找二叉树会有各种不同的高度,最坏会导致查找退化到O(N),所以我们要想构造一种,无论输入是什么,都可以确保其运行时间是对数级别的二叉查找树.我们称其为平衡查找树,我们用得最多的是一种叫做红黑树,而2-3结点查找树也是一种平衡查找树,其思想与红黑树十分类似,概念上很好理解. 为了要保证树的平衡性,我们做出了一些妥协,允许一个节点有多个键.在2-3树中,一个节点最多可以有两个键,三个链接.每一个链接都对应其中保存的键所分割出来的一个区间.比如说我们有一个节点,键为 10 20 , 那么三个链接的区间就...