紧凑(a,b)树

本文提出一种新的多叉树——紧凑(a,b)树。它通过一种整编操作对树中内结点的儿子和孙子个数之间建立制约关系。在元素个数n→∞,树结点的最大儿子个数b>>4时,使树在最坏情况下的高度和空间利用率都接近最优。它的查找运算比b类树都快,它的更新运算(插入和删除)在折算意义下,即在以整个运算序列的最坏时间为代价下,与b类树的性能相同。