动态有序统计:
主要操作:
OS-Select(i)//返回动态集中第 i 小的元素。
OS-Rank(x) //返回动态集排序序列中元素 x 的位置。
新增数据:
在每个结点中保存其子树的结点个数。
size[x]=size[left[x]]+size[right[x]]+1
size[nil]=0
处理 nil 的通用技巧:
标记法,给空结点分配空间,并用一个伪记录内容作为标记。
OS-Select(x,i)(递归函数伪码):
k ← size[left[x]]+1
if i=k then return x
if i<k then return OS-Select(left[x],i)
else return OS-Select(right[x],i-k)
Ex:
OS-Select(root,i) → return ptr to “H”
时间分析:
显而易见,OS-Select(i)、 OS-Rank(x)运行时间为 O(lgn)。
如果直接记录每个结点在动态集排序序列中元素 x 的位置,为维持此数据,红黑树自
身数据结构的操作时间复杂度会比较高。
记录子树结点个数策略下,修改红黑树的插入、删除操作,使其在插入、删除操作中
完成子树结点个数数据项的更新。
Ex(插入“K”):
BST 插入,结点数更新: