19级算法设计与分析期末复习重点
数据结构
红黑树
红黑树的性质
1.本身是一棵二叉查找树
2.每个结点要么是黑色要么是红色
3.树根结点的颜色为黑色
4.叶结点(nil)为黑色
5.如果某个结点为红色，则它的左、右孩子结点均为黑色
6. 对树中任一结点，所有从该结点出发到其叶结点的路径中均包含相同数目的
黑色结点
红黑树的操作及时间
插入：时间复杂度O（lgn）
删除：时间复杂度O（lgn）
查找结点，找前驱、后继：时间复杂度O（lgn）
红黑树的应用
序统计树
概念
序统计就是在一系列数中找出最大、最小值，某个数的序值等操作。
解决动态序统计问题
Size[x]域的定义为：以x为根的子树所包含的内部结点数(包括x本身)
Size[x]=Size[x.le]+Size[x.right]+1
找第i个最小值操作：算法时间：O(lgn)
求x的序值操作：算法时间：O(lgn)
完成一次插入或删除操作：时间为O(lgn)
区间树
概念
关键字=区间的低端点
新增域int：区间的端点值
新增域max：x.max=Max(x.int.high, x.le.max, x.right.max )
查找操作：算法时间O(lgn)
数据结构的扩张步骤
剩余14页未读，继续阅读
评论0