- 论坛徽章:
- 0
|
说一下我以前想过的一个方法:
删除可以分两种情况来讨论：1.要删除节点是叶节点；2.要删除节点不是叶节点。
1。是叶节点的情况
假设要删除的节点为T。这种情况可以直接删除此节点。需要注意的是，如果T有父节点（即avl树不是一棵只有单个节点的树），需要将T的父节点中指向T的指针置为0。如果删除T节点导致其父节点不再平衡，需要调整其父节点（也就是旋转）。这种调整可能一直持续到根节点。
2。不是叶节点的情况
假设要删除的节点为T。删除的思路是：
a. 找到T的左子树的最右节点或者右子树的最左节点，记为T1。
b. 将T1的数据值赋给T。
c. 判断T1是否为叶节点。如果是，设置其父节点的指针；否则，T1一定是下面两种情况。
这时可以将T2的各中信息都复制给T1。相当于T2上移至T1的位置，同时删除T1。
d. 判断T1的父节点是否平衡，如果不平衡则需要调整父节点。这种调整也可能一直持续到根结点。
实现方式：
因为删除一个节点可能导致对其祖先结点的旋转，因此可以事先将要节点的祖先节点都保存下来。也就是从根结点到T1节点的路径。调整的时候是从T1的父节点开始往山（可能持续到根节点），因此其路径适合保存在栈中。这样可以依次从栈中弹出节点，判断是否需要调整。
需要注意的是，如果T1不是叶节点，需要查找其左子树的最右节点或者右子树的最左节点T2，这时的调整是从T2的父节点开始的，因此还需要记录T1到T2的路径，也就是说，最终得到的路径是从根结点到T2的。
调整某个节点的时候，记此节点为Tc，假设其父节点为Tp。需要将Tp的左（或者右）子树指针指向调整后得到的新Tc。
这只是思路, 以前写过一个代码,可以看下面的连接. 不过没有经过严格测试. 说不定有什么问题.
不知道怎么直接添加图片,可以看这里http://www.cppblog.com/lucency/archive/2007/09/28/33098.html |
|
免费注册
发表于 2007-12-06 15:18
LZ有前途，我很看好你哦~
