首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》二叉查找树

关灯直达底部

在内存中进行二分查找的效率我们已经看到了,非常高效。但是,当查找集合频繁地变动时,二分查找的效率退化得非常严重。如果需要处理动态的数据集合,我们需要采用一种不同的数据结构来得到可以接搜的查找性能。

要存储动态的查找数据集合的话,查找树可能是最常用的数据结构了。无论是在内存中还是在二级存储器上,查找树的性能都非常优秀。最经常使用的查找树是二叉查找树,其每一个内部节点都有两个子节点。另外一种查找树——B树,是一棵n元树,是属于磁盘上的数据结构。

输入/输出

使用了查找树之后的输入和输出和二分查找的一样。集合C中每一个元素e都将被存储到查找树中,并且这些元素都需要有一个或者更多的属性能够作为键值,这些键值决定了全集U。元素也必须有能够区分它们的属性。查找树将会存储C中的元素。