06.二叉搜索树（二）

根据传入的元素删除

• 步骤：

1.根据传入的元素先找到其节点。

	
    public Node node(E element){
        Node  node = root;
        while( node != null ){
            int res = compare(element, 		       node.element);
            if (res == 0) return node;
            else if( res > 0 ){
                node = node.right;
            }else{
                node = node.left;
            }
        }
        return null;
    }

• 找到删除的节点，这里我们需要分情况来分析：这里有三种情况.

  PS：删除节点都要考虑是左、右以及是否为根节点来分析

  (1):删除的节点为叶子节点

  [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-VGOUPHym-1642573703308)(C:UsersAdministratorAppDataRoamingTyporatypora-user-imagesimage-20220119133013248.png)]

//直接删除 
//1.删除节点为左节点 例：8、10
    node == node.parent.left
    node.parent.left = null
//2.删除节点在右节点
    node == node.parent.right
    node.parent.right = null
//3.删除节点为跟节点
    node.parent == null;
	root = null;

(2):度为1的节点：

//用child替代node的位置
//1.如果node是左子节点
	child.parent = node.parent
    node.parent.left = child;
//2.如果node是右子节点
	child.parent = node.parent
    child.parent.right = child
//3.如果node是根节点
     root = child
     child.parent = null

(3):度为2的节点

• 举例：先删除5，再删除4

• 先用前驱节点或者后继节点的值覆盖原节点的值

• 然后删除相应的前驱或者后继节点

• 如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1和0。

  • 删除节点度为2的做法，是找到它的前驱节点或者后继节点，例如上图要删除的节点为5，按照二叉搜索树的规则要找到一个节点代替5的位置，使其成为一个新的二叉搜索树，那么这个节点就是要删除节点的左子树节点的最大值（前驱节点），或者为右子树的最小值（后继节点）。

上代码：

 public void remove(E element) {
        remove(node(element));
    }
    public void remove(Node node){
        if ( node == null ) return;
        //如果node不等于空
        size--;
        //1.先考虑度为2的节点，
        // 因为是用后继节点的值替换跟节点，
        // 并把后继节点删除（而度为2的后继节点的度必为1或0，所以防止逻辑重叠）
        if(node.hasTwoChildren()){
           Node p =  successor(node);//找后继节点
            //用后继节点的值覆盖该节点
            node.element = p.element;
            //删除后继节点,让后继节点替换node节点，后面会考虑删除度为1的节点
            node =  p ;
        }
        //删除节点node
        // 2.到这一步，此时节点的度必为1或0；
        Node child = node.left != null ? node.left : node.right;
        if (child != null ){// node是度为1的节点
            //更改parent
            child.parent = node.parent;
            //更改parent的left、right的指向
            if( node.parent == null ){//node是根节点,并且度为1
                root = child;
            }
            else if( child == node.parent.left ){//child节点是左节点
                node.parent.left = child;
            }else{
                node.parent.right = child;
            }
        }else if( node.parent == null ){//node是叶子节点，并且是根节点
            root = null;
        }else{//节点为叶子节点
            if(node == node.parent.left){
                node.parent.left = null;
            }else{// node == node.parent.right
                node.parent.right = null;
            }
        }
    }