二叉排序树上删除结点算法的研究

Research on Deleting Node Algorithm of Binary Sort Tree

详细分析了文献[1]中二叉排序树的查找、插入、删除操作.文献[1]先是实现了查找算法,调用查找算法实现插入操作,当查找不成功时插入结点.对于删除操作,是在二叉排序树上查找成功时删除结点,并详细描述了删除结点时的三种情况,其中分析了双亲结点指针的变化,而在具体实现时没有像插入操作那样直接调用查找算法,而是借助于递归和引用控制删除结点和双亲结点的关系及双亲结点指针的变化,在查找的过程中实现删除,边查找边删除.这种不一致性给很多读者带来了疑惑.该文针对该问题提出基于查找算法的删除算法,该算法显式地体现了删除结点时双亲结点指针的变化,一方面和文字描述部分一致,同时又和插入操作具有统一性,便于读者更好地理解二叉排序树上的删除操作.

The article analyzed in detail search,insertion and deletion operation of binary sort tree in Literature 1. Searching algorithm was put forward and insertion operation was realized. Inserting the node when failure in searching. Deletion was carried out when success in search and three cases was describes in detail when deleting nodes,in which analyzing the change of parent node pointer,but not like insertion opera-tion directly call the searching algorithm in realization. It controlled the relations between deleted node and its parent node as well as the change of parent node pointer by means of recursion and reference. Deleting node when searching. The inconsistency makes reader feel discredit. The article puts forward deletion algorithm based on search algorithm,which embodies explicitly the change of parent node point-er when deleting node. This is accord with described part,and unifies with insertion,which is conven-ient for understanding the deletion in binary sort tree.