Search

CN-122021526-A - Method for constructing interval search balanced tree based on batch insertion

CN122021526ACN 122021526 ACN122021526 ACN 122021526ACN-122021526-A

Abstract

A method for searching balance tree based on batch insertion and construction interval comprises the steps of 1) setting element number threshold values of nodes, 2) calculating the node number of a next level according to the total number of nodes of a current level and the element number threshold values of the nodes, 3) sorting all the nodes of the current level along an X axis, dividing the nodes with similar positions into a plurality of columns according to an X axis sorting result, 4) sorting the nodes of each column along a Y axis, dividing the nodes with similar positions in each column into a plurality of sections according to a Y axis sorting result, inserting the nodes of each section into a father node, and 5) processing all the father nodes until a root node in the next level in a recursion mode to obtain the balance tree. The method can quickly construct the interval search balance tree, and effectively improves the efficiency of area search initialization and batch operation processing elements.

Inventors

  • HE RENDONG
  • CHEN GANG
  • ShangGuan Yingjun
  • TAN XIAOHUI

Assignees

  • 南京集成电路设计服务产业创新中心有限公司

Dates

Publication Date
20260512
Application Date
20241111

Claims (9)

  1. 1. A method for constructing an interval search balanced tree based on batch insertion, comprising: Step 1), setting element quantity threshold values of nodes; Step 2), calculating the number of nodes of the next level according to the total number of nodes of the current level and the element number threshold value of the nodes; Step 3), ordering all the nodes of the current level along the X axis, and dividing the nodes with similar positions into a plurality of columns according to the ordering result of the X axis; step 4), sorting the nodes in each column along a Y axis, dividing the nodes in each column with similar positions into a plurality of sections according to a Y axis sorting result, and inserting the nodes in each section into a father node; and 5) processing all the father nodes in the next level in a recursion mode until reaching a root node to obtain a balanced tree.
  2. 2. The method of constructing a section search balanced tree based on batch insertion of claim 1, wherein the number of nodes of the next level is greater than or equal to the total number of nodes of the current level divided by an element amount threshold of the nodes.
  3. 3. The method for searching a balanced tree based on batch insertion and construction of an interval according to claim 1, wherein the step 3) further comprises: calculating the number of columns and segments: K=sqrt(L); Where K represents the number of columns, the number of segments, L represents the calculated number of nodes of the next level, and sqrt () represents the square root.
  4. 4. The method for searching a balanced tree based on batch insertion and construction interval according to claim 1, wherein the step 5) further comprises: recursively processing the nodes of each level step by step; When the number of nodes transferred to the next level is larger than the element number threshold of the nodes, sequentially recursively calling the step 3) and the step 4), and completing the node creation operation of the next level; when the number of nodes transferred to the next level is less than the element number threshold of the nodes, all the nodes of the current level are directly inserted into the root node to serve as first-level child nodes, and the bottom-up balanced tree construction operation is finished.
  5. 5. The method for constructing a section search balanced tree based on batch insertion according to claim 1, wherein for the movement, deletion and modification of the batch elements, the use condition of batch insertion is set such that when the element proportion of modification or deletion is higher than a preset proportion in the section search data structure, the batch insertion is selected to be used for reconstructing the balanced tree.
  6. 6. The method of claim 1, wherein the steps of sorting all the nodes of the current hierarchy along the X-axis and sorting the nodes of each column along the Y-axis are sorting the center point of each node along the X-axis and the Y-axis, respectively.
  7. 7. The method for searching a balanced tree based on batch insertion and construction of an interval according to claim 1, wherein the step 2) further comprises: for the initial current level, the nodes are the graphic elements of the circuit; and calculating the number of nodes of the next level according to the total number of the graphic elements and the element number threshold value of the nodes.
  8. 8. An electronic device comprising a memory, a processor, and a computer program stored in the memory and executable on the processor, wherein the processor is configured to execute the computer program stored in the memory to implement the method steps of any one of claims 1-7 for searching a balanced tree based on a batch insertion build interval.
  9. 9. A computer readable storage medium, characterized in that the storage medium has stored therein a computer program, which is loaded and executed by a processor to implement the method steps of any of claims 1-7 for searching balanced trees based on batch insertion build intervals.

Description

Method for constructing interval search balanced tree based on batch insertion Technical Field The invention relates to the technical field of ultra-large scale analog integrated circuit design, in particular to a method for searching a balance tree based on batch insertion construction interval. Background With the increasing integration of analog integrated circuits, the scale of circuit elements is increasing, and the efficiency of interval searching also greatly influences the operation smoothness and the working efficiency of users using electronic design automation software. Electronic design automation (Electronic Design Automation, EDA) tools used in very large scale analog integrated circuit designs place higher demands on the start-up efficiency and search efficiency of the interval search. In the analog circuit design stage, region inquiry is one of important functions of layout viewing and modification. The basic principle of interval searching is to search various graphic objects intersecting with a search box in a designated search area, and to have different application scenes, such as selecting elements in a certain area by a box in an editor interface and drag and delete the elements, or to view elements in a design according to designated levels in a multi-level scene. In order to ensure the accuracy of the query result, the stored data in the regional query before the query needs to be guaranteed to be in the latest state, so that when the graphic element is updated (created, changed in size and position and deleted), information is transferred to the regional query module so as to update the graphic element information in the regional query module. Among the area query methods of integrated circuits, a more common method is to use HV tree or Rtree to build a tree. The HV tree is an unbalanced tree, circuit elements are sequentially placed in corresponding subtrees according to the left, middle, right (or up, middle and down), and the HV tree has the advantages of being fast in tree construction, convenient to add and delete and the like, but because the non-leaf node only has 3 child nodes, the memory overhead for tree construction is large, and in addition, a large number of adding and deleting operations can cause the reduction of query performance. Rtree is a balanced tree, and a non-leaf node can have a plurality of child nodes, so that the memory overhead of an intermediate node can be reduced, and in addition, for maintaining the balance of the balanced tree, high-efficiency and stable query efficiency can be provided, because the balance of the tree is maintained, and the time cost is high in the process of tree construction and a large number of adding and deleting operations. When Rtree is used as an operation of searching and building a tree in an interval, firstly, adding image elements into an interval searching balance tree structure, wherein each non-leaf node has Min (minimum) to Max (maximum) child nodes, when the child nodes exceed Max nodes, the current node is required to be split into two nodes, in the splitting process, firstly, two nodes farthest in all nodes are required to be selected as starting nodes for splitting two new nodes, and then, the rest nodes are respectively inserted into the new nodes with the minimum area increase after the two nodes until all nodes are inserted into the two new nodes, so that the splitting of the nodes has larger calculation cost. After initialization is completed, interval searching can be performed, a user needs to enter an area to be searched, the interval searching module sequentially traverses all intersected sub-nodes of a root until traversing is completed, and intersected circuit elements are returned to the user. The user can check, move, modify, delete and other related operations on the circuit elements searched for the interval, and the related operations such as moving or deleting the elements need to remove the corresponding elements from the data structure searched for the interval. In the algorithm, under the condition that the circuit element order is continuously increased, a large number of splitting operations are needed when the interval search is performed by Rtree for building the tree, a large number of time-consuming operations such as sequencing distance calculation are included, the problems of low loading speed, high maintenance cost of the balanced tree and the like exist, and in addition, the same problems exist in operations such as moving and deleting batch elements, so that the related performance of the interval search needs to be further improved. Disclosure of Invention In order to solve the defects of the prior art, the invention aims to provide a method for searching a balance tree based on batch insertion and construction interval, which is used for assembling similar image elements based on characteristic analysis of the image elements, and rapidly inserting the image elements in batches fro