给定大量的ip段的记录信息[起始ip,终止ip]
(1)提供判定ip是否存在有对应的段记录
(2)提供特定ip所属的所有的ip段记录
首先将所有的记录读取到数组中
将所有start_ip,end_ip进行排序,将整个ip地址空间划分出来
将包含关系的区段进行拆分分裂成新的区段,将部分重叠的区段中公共部分和各自独立部分分裂成独立的区段
上面的区段有逻辑的,也可能是刚好是物理的,这个也需要区分出来
针对重叠或包含区就需要记录包含它的所有的物理区段在数组中的位置,用数组或者列表保存
将全局区间中值附近的区段分为2部分,构成二叉树的左子树与右子树,构造全局的空间段temp的根节点,根节点记录左区段的最大ip,以及右区段的最小ip
逐步按照递归的方法,将划分的左区间进一步划分构成一颗二叉树
此二叉树只是记录的区段的索引信息,以及构成树的一些必要参数,具体的物理区段对象在数组中
判定ip是否存在区段的方式就是遍历二叉树,如果ip在根节点的左区段最大值与右区段的最小值范围内,则表示ip没有物理区段描述
判定包含ip的所有的物理区段,直接遍历二叉树,找到满足范围的树节点,然后得到节点中的物理区段的索引列表
阅读(962) | 评论(0) | 转发(0) |
