二叉树并行查找方法和设备

摘要

本发明实施例涉及二叉树并行查找方法和设备。二叉树并行查找方法包括：以选定的子树阶数将二叉树分成多个子树；为每个子树构造共同关键字，包括：从每个子树的每个节点数据的最高位起，提取子树中全部节点数据的相同的高位数据，作为该子树的子树共同关键字；据根据子树的共同关键字的位数，从待查数据构造待查高位关键字，包括：按照共同关键字的位数，从最高位起，提取待查数据的高位数据，作为待查高位关键字；比较待查高位关键字与子树共同关键字，在待查高位关键字与子树共同关键字的比较结果不相等时，根据比较结果确定下一次查找的子树方向，如果相等，则根据并行关键字的比较确定下一次查找的子树方向。根据本发明实施例，将二叉树压缩为低阶数的子数以降低目标查找树的高度，提取每个子树的共同关键字并为每个子树构造并行查找关键字，可以大大减少对数据存储区的访问次数，提高查找效率。

主权项

一种有序二叉树并行查找方法，其特征在于，以选定的子树阶数将所述二叉树分成多个子树，所述子树阶数大于或等于3；为每个子树构造共同关键字，包括：从每个子树的每个节点数据的最高位起，提取所述子树中全部节点数据的相同的高位数据，作为该子树的子树共同关键字；根据所述子树的共同关键字的位数，从待查数据构造待查高位关键字，包括：按照所述共同关键字的位数，从最高位起，提取待查数据的高位数据，作为待查高位关键字；比较所述待查高位关键字与所述子树共同关键字，在所述待查高位关键字与所述子树共同关键字的比较结果不相等时，根据比较结果直接确定下一次查找的子树方向。