删除结点的处理方法 1)若是叶子结点，直接删除 2)只有一个孩子，则将其孩子直接挂到其双亲上。 3)有两个孩子，找左孩子中最大的一个元素，代替被 删除结点，最大元素肯定只有一个孩子，按2)处 理删除最大元素 Status Delete BST(BiTree &T,KeyType kval) ·二叉查找树的平均查找长度 p (n)=2 (n+1)/n *logn+C 二叉平衡（查找）树 - 树中每个结点的左、右子树深度之差的绝对值不大 于1，这种平衡状态的二叉查找树。实现方法：平 衡旋转技术 ypb@ustc.edu.cn 10 中国科学技术大学ypb@ustc.edu.cn 10 中国科学技术大学 • 删除结点的处理方法 1)若是叶子结点，直接删除 2)只有一个孩子，则将其孩子直接挂到其双亲上。 3)有两个孩子，找左孩子中最大的一个元素，代替被 删除结点，最大元素肯定只有一个孩子，按2）处 理删除最大元素 – Status Delete_BST(BiTree &T, KeyType kval) • 二叉查找树的平均查找长度 p（n）＝2（n＋1）/n *logn+C • 二叉平衡（查找）树 – 树中每个结点的左、右子树深度之差的绝对值不大 于1，这种平衡状态的二叉查找树。实现方法：平 衡旋转技术