二叉查找树查找、增加、删除

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

下面是二叉查找树的常用操作（kotlin编写）：

class TreeNode<T> {
    var data: T? = null
    var left: TreeNode<T>? = null
    var right: TreeNode<T>? = null
}

class BinearySeachTree {

     var tree: TreeNode<Int>? = null

    /**
     * 查找元素
     */
    fun find(data: Int): TreeNode<Int>? {
        var p: TreeNode<Int>? = tree
        while (p != null) {
            p.data?.let {
                if (data < it) {
                    p = p?.left
                } else if (data > it) {
                    p = p?.right
                } else {
                    return p
                }
            }
        }
        return null
    }

    /**
     * 插入数据
     */
    fun insert(data: Int) {
        tree?.let {
            var p: TreeNode<Int>? = it
            while (p != null) {
                if (data > p.data ?: 0) {
                    if (p.right == null) {
                        p.right = TreeNode(data)
                        return
                    }
                    p = p.right
                } else {
                    if (p.left == null) {
                        p.left = TreeNode(data)
                        return
                    }
                    p = p.left
                }
            }
            return
        }
        tree = TreeNode(data)
    }

    /**
     * 删除数据
     */
    fun delete(data: Int) {
        var p: TreeNode<Int>? = tree    //先查找要删除的节点是否存在
        var pp: TreeNode<Int>? = null   //要删除的节点的父节点
        while (p != null) {
            if (data == p.data) {
                break
            }
            pp = p
            if (data > p.data ?: 0) {
                p = p.right
            } else {
                p = p.left
            }
        }
        //没有找到该节点
        if (p == null)
            return

        //如果待删除节点的左、右子节点都不为空
        if (p.left != null && p.right != null) {
            //先找到右子树的最小节点
            var minP = p.right!!            //用 minP 记录右子树最小节点
            var minPP: TreeNode<Int>? = p   //minPP 是 minP 的父节点
            while (minP.left != null) {
                minPP = minP
                minP = minP.left!!
            }
            //交换待删除节点与其右子数最小节点的值
            p.data = minP.data
            //现在只需删除 minP 节点了，minP节点必然是叶子节点或是只有一个右子节点了
            p = minP
            pp = minPP
        }

        //如果删除的是叶子节点，或者只有一个子节点
        var child: TreeNode<Int>? = null
        if (p.left != null) {
            child = p.left
        } else if (p.right != null) {
            child = p.right
        } else {
            child = null
        }

        if (pp == null) {
            //删除的是根节点
            tree = child
        } else if (pp.left == p) {
            pp.left = child
        } else {
            pp.right = child
        }
    }

}

二叉查找树的查找、增加、删除操作的时间复杂度与树的高度有关，如果是一棵平衡二叉查找树，则其时间复杂度均为 O(logn)，如果树退化成一个链表，则其时间复杂度为最坏情况 O(n)