（8）Go实现二分搜索树-删除任意节点

https://www.jianshu.com/p/de46dcebada3
继上一篇《Go--二分搜索树1--前中后序递归》的后续

找出最小值，最大值，删除最小值，最大值，删除任意节点的非递归算法和递归算法实现
// 找出最小值，并将该值返回，非递归算法
func (tree *node) FindMinVal() *int {
    if tree.value == nil {
        return nil
    }

    buf := tree
    for {
        if buf.Left.value == nil {
            return buf.value
        }
        buf = buf.Left
    }
}

// 找出最小值，并将该值返回，递归算法
func (tree *node) FindMinVal2() *int {
    if tree.Left.value == nil {
        return tree.value
    }

    return tree.Left.FindMinVal2()
}

// 找出最大值，并将该值返回，非递归算法
func (tree *node) FindMaxVal() *int {
    if tree.value == nil {
        return nil
    }

    for {
        if tree.Right.value == nil {
            return tree.value
        }
        tree = tree.Right
    }
}

// 找出最大值，并将该值返回，递归算法
func (tree *node) FindMaxVal2() *int {
    if tree.Right.value == nil {
        return tree.value
    }

    return tree.Right.FindMaxVal2()
}

// 删除最小值并将该值返回，非递归算法
func (tree *node) DeleteMinVal() *int {
    if tree.value == nil {
        return nil
    }

    for {
        if tree.Left.value == nil {
            v := tree.value

            // 这里如果写成 tree = tree.Right 执行后外面tree不会变
            *tree = *tree.Right
            return v
        }
        tree = tree.Left
    }
}

// 删除最小值并将该值返回，递归算法
func (tree *node) DeleteMinVal2() *int {
    if tree.value == nil {
        return nil
    }

    if tree.Left.value == nil {
        v := tree.value
        *tree = *tree.Right
        return v
    }
    return tree.Left.DeleteMinVal2()
}

// 删除最大值并将该值返回，非递归算法
func (tree *node) DeleteMaxVal() *int {
    //if tree.value == nil {
    //  return nil
    //}

    for {
        if tree.Right.value == nil {
            v := tree.value
            *tree = *tree.Left
            return v
        }
        tree = tree.Right
    }
}

// 删除最大值并将该值返回，递归算法
func (tree *node) DeleteMaxVal2() *int {
    if tree.value == nil {
        return nil
    }

    if tree.Right.value == nil {
        v := tree.value
        *tree = *tree.Left
        return v
    }
    return tree.Right.DeleteMaxVal2()
}

删除搜索树的任意节点分为以下几种情况：
（1）节点为叶子节点，直接将该节点删除；
（2）节点只有左子树右子树为空，则将该节点的左子树替换到该节点位置，即 tree = tree.left；
（3）节点只有右子树左子树为空，则将该节点的右子树替换到该节点位置，即 tree = tree.right；
（4）节点左右子树都不为空，解决方法由两种：
        1)：节点值替换为右子树中的最小值，并将右子树中的最小值删除；
        2)：节点值替换为左子树中的最大值，并将左子树中的最大值删除；

// 删除给定的值，非递归算法
func (tree *node) DeleteChoose(val *int) {
    for {
        switch {
        // 这里包含两种情况，val不在tree里面，或者tree.value=nil
        case tree.value == nil:
            return
        //  
        case *tree.value == *val:
            if tree.Right.value == nil {
                // 这里包含2中情况，left为nil和不为nil
                *tree = *tree.Left
                return
            }
            // DeleteMinVal()：删除tree中的最小值，并将最小值返回
            tree.value = tree.Right.DeleteMinVal()
            return
        case *tree.value > *val:
            tree = tree.Left
        case *tree.value < *val:
            tree = tree.Right
        }
    }
}

// 删除给定的值，递归算法
func (tree *node) DeleteChoose2(val *int) {
    // 如果不加这个判定，删除的数值不在tree里面会报错
    if tree.value == nil {
        return
    }

    if *tree.value == *val {
        // DeleteMinVal2()：删除tree中的最小值，并将最小值返回
        tree.value = tree.Right.DeleteMinVal2()
        return
    }

    if *tree.value > *val {
        tree.Left.DeleteChoose2(val)
        return
    }
    if *tree.value < *val {
        tree.Right.DeleteChoose2(val)
    }
}

测试算法
先定义一个tree的中序遍历打印方法
// 中序遍历打印tree
func (tree *node) Print() {
    buf := []int{}
    tree.TraverseInOrder(&buf)
    fmt.Println("中序遍历结果：", buf)
}

测试代码
func main() {
    b := fork_tree1.NewNode()
    b.Add2(20)
    for i := 0; i < 20; i++ {
        b.Add2(rand.Intn(40))
    }

    b.Print()
    fmt.Printf("非递归找出最小值：%d\n", *b.FindMinVal())
    fmt.Printf("递归找出最小值：%d\n", *b.FindMinVal2())
    fmt.Printf("非递归找出最大值：%d\n", *b.FindMaxVal())
    fmt.Printf("递归找出最大值：%d\n", *b.FindMaxVal2())
    b.Print()
    fmt.Println("--------")
    fmt.Printf("非递归删除最小值：%d\n", *b.DeleteMinVal())
    b.Print()
    fmt.Printf("递归删除最小值：%d\n", *b.DeleteMinVal2())
    b.Print()
    fmt.Printf("非递归删除最大值：%d\n", *b.DeleteMaxVal())
    b.Print()
    fmt.Printf("递归删除最大值：%d\n", *b.DeleteMaxVal2())
    b.Print()
    fmt.Println("--------")
    v1 := 40
    v2 := 20
    b.DeleteChoose(&v1)
    fmt.Println("非递归删除40:")
    b.Print()
    b.DeleteChoose(&v2)
    fmt.Println("非递归删除20:")
    b.Print()
    v1 = 36
    v2 = 14
    b.DeleteChoose2(&v1)
    fmt.Println("递归删除36:")
    b.Print()
    b.DeleteChoose2(&v2)
    fmt.Println("递归删除14:")
    b.Print()
}

测试输出结果
中序遍历结果： [1 2 5 7 8 9 11 14 16 19 20 25 26 31 34 37 38]
非递归找出最小值：1
递归找出最小值：1
非递归找出最大值：38
递归找出最大值：38
中序遍历结果： [1 2 5 7 8 9 11 14 16 19 20 25 26 31 34 37 38]
--------
非递归删除最小值：1
中序遍历结果： [2 5 7 8 9 11 14 16 19 20 25 26 31 34 37 38]
递归删除最小值：2
中序遍历结果： [5 7 8 9 11 14 16 19 20 25 26 31 34 37 38]
非递归删除最大值：38
中序遍历结果： [5 7 8 9 11 14 16 19 20 25 26 31 34 37]
递归删除最大值：37
中序遍历结果： [5 7 8 9 11 14 16 19 20 25 26 31 34]
--------
非递归删除40:
中序遍历结果： [5 7 8 9 11 14 16 19 20 25 26 31 34]
非递归删除20:
中序遍历结果： [5 7 8 9 11 14 16 19 25 26 31 34]
递归删除36:
中序遍历结果： [5 7 8 9 11 14 16 19 25 26 31 34]
递归删除14:
中序遍历结果： [5 7 8 9 11 16 19 25 26 31 34]

//
二分搜索树的时间复杂度分析
h 表示二分搜索数的高度，n 表示节点数量
对于满的二分搜索数，h = log2(n+1) = O(log2(n))
增add：O（h）        查contains：O（h）        删del：O（h）
logn 和 n 的差距
            logn    n
n =16       4       16      相差4倍
n =1024     10      1024    相差100倍
n =100万    20      100万    相差5万倍

logn是平均的情况，在最坏的情况下，搜索树只有单边
有数据，这样节点数量会等于高度，即n=h，在最坏的
情况下，时间复杂度为O(n)
解决这种情况的方法是平衡二叉树，待更新...

有bug欢迎指出，转载请注明出处。