© 1999-2048 dssz.net 粤ICP备11031372号
[C/C++] Splay Tree
说明: 伸展树的主要特点:每次访问某个节点时,都把此节点旋转到根部。保证从空树开始任意M次操作最多花费O(MlogN)的时间,也就是说它的摊还时间为O(F(N))。 伸展数的主要难点:展开函数的实现。 基本操作插入、删除、查找都和展开函数相关。 插入:在根处按要插入的元素展开树,如果树中已经存在此节点,则此节点在展开后就是根;如果不存在节点,根处的元素是比欲插入节点小的最大节点或比之大的最小节点。插入时则把元素插入根处! 删除:按欲删除的元素展开根,如果此元素存在,则根就是它。删除就删除它吧!^_^请<ninghuan001> 上传 | 大小:3kb