严格平衡二叉排序树及其构造

Strict Balanced Binary Sort Tree and its Construction

论文对一直沿用至今的平衡二叉树和平衡二叉排序树概念的合理性提出质疑,给出了二叉树结点的严格平衡因子和严格平衡二叉树及严格平衡二叉排序树的新概念。论文给出的构造严格平衡二叉排序树的递归算法及二叉排序树元素插入和删除的严格平衡化过程比动态构造平衡二叉排序树的传统Adelson-Velskii和Landis算法更加简单而自然。

In this paper reasonableness of the concept of the balanced binary tree and the balanced binary sort tree up to now in general use has been called in question,and new concept of strict balance factor,strict balanced binary tree and strict balanced binary sort tree has been presented.In this paper given recursive algorithm of constructing the strict balanced binary sort tree and process of strict balancing under inserting and deleting element in the binary sort tree are more simple and natural than traditional Adelson-Velskii & Landis' algorithm of dynamic constructing the balanced binary sort tree.