一种基于二分边界值计算的非平衡二叉树构造方法

摘要

一种基于二分边界值计算的非平衡二叉树构造方法，该方法的二叉树中每个结点包含一个整数键值，向二叉树插入新增结点时，若新增结点与二叉树中结点的键值不相等，则必存在一个小的键值A和一个大的键值B，先根据键值A和B计算二分边界值C，再根据二分边界值C确定新增结点与二叉树中结点的关系以及插入新增结点的路径。二分边界值C＝N×F，其中N为奇数，F为2的X次幂，X为整数。二分边界值C必须使键值A和B满足(N﹣1)×F﹤A≦N×F同时N×F≦B﹤(N﹢1)×F。本发明具有简单快速的明显优势，且内存消耗小，更适合频繁添加和删除结点的应用场景。