平衡二叉树的删除节点
c语言吧
全部回复
仅看楼主
level 5
怒人水瓶 楼主
平衡二叉树删除某个节点后，怎么查找高度最低的那个失衡节点，
如下图，我要删除55
2022年11月20日 13点11分 1
level 5
怒人水瓶 楼主
删除55后的二叉搜索树
2022年11月20日 13点11分 2
level 5
怒人水瓶 楼主
此时高度最低的不平衡节点是70，我该怎么做才能找到这三个节点
2022年11月20日 13点11分 3
怒人水瓶
复杂度期望不要太高，如果把每个节点都遍历一遍，就失去了使用平衡二叉树的初衷了
2022年11月20日 13点11分
level 5
怒人水瓶 楼主
2022年11月20日 13点11分 4
level 5
怒人水瓶 楼主
我的思路是，先把要删除的节点的父节点和父节点的父节点的指针收集起来备用，这儿实际删除的是65，将70节点和55节点的指针存入数组
2022年11月22日 07点11分 5
level 5
怒人水瓶 楼主
删除65后，刷新一下70及其子节点的高度，判断70是否平衡，如果平衡，二叉树平衡，如果不平衡调整平衡，再刷新55节点极其子节点的高度，判断55节点是否平衡，不平衡则平衡这颗子树，最后刷新根节点到55节点直接每个节点的高度
完毕
2022年11月22日 07点11分 6
1