基于树形数据结构节点的插入的方法和存储装置

摘要

本发明实施例公开了一种基于树形数据结构节点的插入的方法和存储装置。根据待插节点的关键码值在主树中查找最近主树节点，所述最近主树节点的关键码值小于且最接近待插节点的关键码值；以最近主树节点的外部指针指向的从树作为当前从树，判断当前从树是否已满，若是，则在当前从树中任意选择一个节点作为拆分节点，将拆分节点插入到主树中作为新建主树节点，为新建主树节点分配新建从树，并将新建主树节点的外部指针指向新建从树，将当前从树中位于拆分节点左侧的全部节点搬移到新建从树中，然后执行查找最近主树节点，若否，则将待插节点插入到当前从树中。将树形数据结构的树分成主树和从树降低了树的高度，减少了节点插入的时间。

主权项

一种基于树形数据结构节点的插入方法，其特征在于，包括：通过路由器的输入端口接收报文，并获得所述报文的关键码值；根据待插节点的关键码值在主树中查找最近主树节点，所述最近主树节点的关键码值小于且最接近待插节点的关键码值；所述主树的根节点初始化为具有最小的关键码值；其中，所述主树包括父节点、所述父节点的左子节点和所述父节点的右子节点，且所述左子节点大于所述父节点，所述父节点大于所述右子节点；以最近主树节点的外部指针指向的从树作为当前从树，判断当前从树是否已满，若是，则在当前从树中任意选择一个节点作为拆分节点，将拆分节点插入到主树中作为新建主树节点，为新建主树节点分配新建从树，并将新建主树节点的外部指针指向新建从树，将当前从树中位于拆分节点左侧的全部节点搬移到新建从树中，然后执行查找最近主树节点，若否，则将待插节点插入到当前从树中；所述将待插节点插入到当前从树中包括：将所述关键码值的协议报文插入当前从树中。