平衡二叉树中关于删除最小节点的优化

Question

下面是我的做法:

Answer 1

提问者 慕标8212032 2019-03-23 09:24:31

好的，明白了，谢谢

Answer 2

liuyubobobo 2019-03-23 01:06:00

在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之上节点的改变，产生不平衡：）

继续加油！：）