AVL中这套remove里互斥的逻辑为什么不在BST的时候就优化呢

Question

AVL中这套remove里互斥的逻辑为什么不在BST的时候就优化呢，当时看堆if又if的代码就觉得挺乱的，如果在前面就优化好了，后面看着就不那么难以理解了

Answer 1

提问者 qq_财神_4 2019-01-10 22:35:05

另外老师的课程是我见过的课程中设计得非常循序渐进的了，不然我也不会学到这里了，或许只是我的基本功比较薄，所以我希望能在这里多扣一些基本功相关的问题，可能会让老师看得比较业余，所以请老师见谅

Answer 2

提问者 qq_财神_4 2019-01-10 22:04:42

可能我的表达方式不太好，其实我是想知道以下这段代码

else { //key.compareTo(node.key)==0

            //待删除节点左子树为空情况

            if (node.left == null) {

                Node rightNode = node.right;

                node.right = null;

                size--;

                retNode = rightNode;

            }

            //待删除节点右子树为空情况

            else if (node.right == null) {

                Node leftNode = node.left;

                node.left = null;

                size--;

                retNode = leftNode;

            }

            else {

......

为啥BST的时候不做if和else的优化，跑测试用例就没出问题，但是跑AVL树的时候的时候就出问题了呢

以下是没优化过的BST的代码——————————————————else { //key.compareTo(node.key)==0

            //待删除节点左子树为空情况

            if(node.left==null){

                Node rightNode=node.right;

                node.right=null;

                size--;

                return rightNode;

            }

            //待删除节点右子树为空情况

            if (node.right==null){

                Node leftNode=node.left;

                node.left=null;

                size--;

                return leftNode;

            }

            //待删左右子树均不为空

            //找到待删节点的后继

            //下面是本节的核心代码

            Node successor =minimum(node.right);//successor后继

            successor.right=removeMin(node.right);//这里已经size--了

            //size++;//真较真要＋回来

            successor.left=node.left;

            node.left=node.right=null;

            //size--;//两相抵消可以不写

            return successor;

• liuyubobobo #1

  我不确定我是不是理解了你的问题。看你的这个帖子：http://coding.imooc.com/learn/questiondetail/96931.html 你已经解决了你的问题了？如果你是指最后待删除左右节点都不为空的代码，为什么一定要用else，那是因为在BST的删除中，前面的情况直接return了。正割函数就结束了。但是AVL树中，没有return回去，还要进行后续的平衡调整，如果不用else，程序在执行完作为空或者右为空的逻辑后，会不正确的执行左右都不为空的逻辑：）

• 提问者 qq_财神_4 回复 liuyubobobo #2

  大概懂了，没使用else的地方全部有return了；其实那个帖子没理解，只是跑没有else的代码会出错所以我才用的else，所以才调了一晚上o(╥﹏╥)o

• liuyubobobo 回复 提问者 qq_财神_4 #3

  哈哈。大赞！这样才有进步啊！继续加油！：）

Answer 3

liuyubobobo 2019-01-10 00:46:04

抱歉，是我的课程没有设计好，不适合你的思路。不管怎样，最终理解了，学到知识，就好啦：）

继续加油！：）

• 提问者 qq_财神_4 #1

  可能我的表达方式不太好，其实我是想知道以下这段代码
  else { //key.compareTo(node.key)==0
  
              //待删除节点左子树为空情况
              if (node.left == null) {
                  Node rightNode = node.right;
                  node.right = null;
                  size--;
                  retNode = rightNode;
              }
              //待删除节点右子树为空情况
              else if (node.right == null) {
                  Node leftNode = node.left;
                  node.left = null;
                  size--;
                  retNode = leftNode;
              }
              else {
  ......
  为啥BST的时候不做if和else的优化，跑测试用例就没出问题，但是跑AVL树的时候的时候就出问题了呢

• 提问者 qq_财神_4 #2

  以下是没优化过的BST的代码——————————————————else { //key.compareTo(node.key)==0
  
              //待删除节点左子树为空情况
              if(node.left==null){
                  Node rightNode=node.right;
                  node.right=null;
                  size--;
                  return rightNode;
              }
              //待删除节点右子树为空情况
              if (node.right==null){
                  Node leftNode=node.left;
                  node.left=null;
                  size--;
                  return leftNode;
              }
              //待删左右子树均不为空
              //找到待删节点的后继
              //下面是本节的核心代码
              Node successor =minimum(node.right);//successor后继
              successor.right=removeMin(node.right);//这里已经size--了
              //size++;//真较真要＋回来
              successor.left=node.left;
  
              node.left=node.right=null;
              //size--;//两相抵消可以不写
              return successor;