平衡二叉树中关于删除最小节点的优化
来源：12-7 从AVL树中删除元素
慕标8212032
2019-03-23
下面是我的做法:
写回答
2回答
-
慕标8212032
提问者
2019-03-23
好的，明白了，谢谢
00 -
liuyubobobo
2019-03-23
在BST下，这么写没问题，虽然这个逻辑不够“好”。说他不够好，是因为，二分搜索树本身是递归性质的。我们的所有的函数，都是在一个局部的子树中把问题解决，而不牵连这个子树外的任何内容。
比如remove(Node node, K key), 是在以node为根节点的二分搜索树中删除K；
Node getNode(Node node, K key)，是在以node为根节点的二分搜索树中寻找K；
add(Node node, K key)，是在以node为根节点的二分搜索树中插入K。
但是，你的逻辑中，将root引入进来，使得这个函数操作的对象不仅仅是在以node为根节点的二分搜索树的范围内了。
----------
而在AVL树中，由于有平衡调整机制，这么做将直接导致维护平衡的失败。
要注意，我们整个平衡调整机制，都是建立在：维护了当前的以node为根节点的AVL树的平衡，就会保持整棵树的平衡。
但是，现在，如果直接从root的角度把successor.key删除，这个操作，将对正科二分搜索树维持一遍平衡。其中，也包括你现在所关注的node之上的节点。而对node之上的节点的改变，会使得我们所设计的维护node之下的节点的平衡的逻辑，结合node之上节点的改变，产生不平衡：）
继续加油！：）
00
相似问题