Title:
UNBALANCED BINARY TREE CONSTRUCTION METHOD BASED ON CALCULATION OF BINARY BOUNDARY VALUE
Document Type and Number:
WIPO Patent Application WO/2020/083062
Kind Code:
A1
Abstract:
Disclosed is an unbalanced binary tree construction method based on the calculation of binary boundary value. According to the method, each node of the binary tree contains an integer key value. When a new node is inserted into the binary tree, if the new node has a key value not equal to the key value of a node in the binary tree, there are necessarily a smaller key value A and a greater key value B. First, the binary boundary value C is calculated on the basis of the key values A and B; then, the relation between the new node and the node in the binary tree as well as the route for the new node to be inserted are determined based on the binary boundary value C. If A≠0, there must be an odd integer N and an integer power F of 2 for the key values A and B to satisfy (N﹣1)×F﹤A≦N×F and N×F≦B﹤(N﹢1)×F, then the binary boundary value C＝N×F; and if A=0, then the binary boundary value C is equal to 0. The method has the remarkable advantages of simplicity, rapidness and low memory consumption, and is suitable for application scenes where nodes are added and deleted frequently.
Inventors:
LONG HUI (CN)
GUAN ZHIJIAN (CN)
GUAN ZHIJIAN (CN)
Application Number:
PCT/CN2019/111033
Publication Date:
April 30, 2020
Filing Date:
October 14, 2019
Export Citation:
Assignee:
CHANGSHA XINHONG SOFTWARE LTD (CN)
International Classes:
G06F8/20
Foreign References:
| CN109445763A | 2019-03-08 | |||
| US5230047A | 1993-07-20 | |||
| CN105787126A | 2016-07-20 | |||
| CN101788990A | 2010-07-28 |
Other References:
朱毅 等 (ZHU, YI ET AL.): "用于细粒度完整性度量的非平衡二叉哈希树模型 (Non-balanced Binary Hash-Tree Model for Fine-Grained Integrity Measurement)", 小型微型计算机系统 (JOURNAL OF CHINESE COMPUTER SYSTEMS), vol. 35, no. 7, 31 July 2014 (2014-07-31), XP055708689
荣星 等 (RONG, XING ET AL.): "基于双层非平衡散列树的云平台远程验证方案 (Remote Attestation Scheme for Cloud Platform Based on Double-Layer Unbalanced Hash Tree)", 通信学报 (JOURNAL ON COMMUNICATIONS), vol. 38, no. 9, 30 September 2017 (2017-09-30), XP055708690
OLIVIER, STEPHEN ET AL.: "UTS: An Unbalanced Tree Search Benchmark", LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING, 4 November 2006 (2006-11-04), XP019079666
荣星 等 (RONG, XING ET AL.): "基于双层非平衡散列树的云平台远程验证方案 (Remote Attestation Scheme for Cloud Platform Based on Double-Layer Unbalanced Hash Tree)", 通信学报 (JOURNAL ON COMMUNICATIONS), vol. 38, no. 9, 30 September 2017 (2017-09-30), XP055708690
OLIVIER, STEPHEN ET AL.: "UTS: An Unbalanced Tree Search Benchmark", LANGUAGES AND COMPILERS FOR PARALLEL COMPUTING, 4 November 2006 (2006-11-04), XP019079666
Attorney, Agent or Firm:
CHANGSHA SHI BIAOZHI PATENT AGENCY (Room 801 Shi Dai Guo Ji,,No. 138 Tong Zi Po Xi Road, Yuelu District, Changsha Hunan 5, CN)
Download PDF: