二叉搜索树

也叫二叉排序树，它的递归定义为：
1.如果树T的左子树非空，则左子树中的所有结点的值小于T的根节点的值；
2.如果树T的右子树非空，则右子树中的所有结点的值大于T的根节点的值；
3.树T的左子树和右子树均为二叉搜索树

例子：

这棵树不是二叉搜索树

二叉搜索树的创建

算法思想：先树中搜索插入的key是否存在，如果存在就用当前的value替换树中的value，如果不存在，就在最后的位置插入一个结点

创建树结点的类：

public class BinarySearchNode<V> {
    public int key;
    public V value;
    public BinarySearchNode<V> leftNode;
    public BinarySearchNode<V> rightNode;

    public BinarySearchNode(int key, V value) {
        this.key = key;
        this.value = value;
    }
}

设定key为整型，value为指定的类型

创建二叉搜索树的类：

public class MyBinarySearchTree<V> {
    private BinarySearchNode<V> root = null;
}

具体算法：
1.判断树是不是空树，如果是空树就创建一根结点

if (root == null) {
    root = new BinarySearchNode<V>(key, value);
    return;
}

2.如果不是空树，遍历一下树，找一下树中有没有跟插入的数据相同的结点，如果有，修改一下值，如果没有就插入，所以需要记录当前结点的父结点，因为最后是插在父结点的位置上

BinarySearchNode<V> cur = root;
BinarySearchNode<V> parent = null;
while (cur != null) {
     if (key < cur.key) {
         parent = cur;
         cur = cur.leftNode;
     } else if (key > cur.key) {
         parent = cur;
         cur = cur.rightNode;
     } else {
     	 // 找到了相同key的结点
     	 // 修改结点的值即可
         cur.value = value;
         return;
     }
}

3.循环结束，没有相同的值，在父结点的位置上进行插入一个结点

if (key < parent.key) {
    parent.leftNode = new BinarySearchNode<V>(key, value);
} else {
    parent.rightNode = new BinarySearchNode<V>(key, value);
}

最后的插入函数：

public void insert(int key, V value) {
        if (root == null) {
            root = new BinarySearchNode<V>(key, value);
            return;
        } else {
            BinarySearchNode<V> cur = root;
            BinarySearchNode<V> parent = null;
            while (cur != null) {
                if (key < cur.key) {
                    parent = cur;
                    cur = cur.leftNode;
                } else if (key > cur.key) {
                    parent = cur;
                    cur = cur.rightNode;
                } else {
                    cur.value = value;
                    return;
                }
            }
            if (key < parent.key) {
                parent.leftNode = new BinarySearchNode<V>(key, value);
            } else {
                parent.rightNode = new BinarySearchNode<V>(key, value);
            }
            return;
        }
    }

图示：
对这颗树插入key = 18的结点

18小于cur所指向的结点的key
即 18 < 20
所以在左子树进行查找

16 < 18 所以在右子树查找

此时cur的右子树为空，所以要插入一个结点
插入的位置是parent的右子树

二叉搜索树的删除

算法思想：
设cur为当前要被删除的结点，parent为cur的父结点
1.cur结点没有左子树 （cur.left == null）
1.1 cur是根结点 （cur == root）

删除操作：

root = cur.right;

1.2 cur不是根结点，cur是parent的右子树
（cur != root && cur == parent.right）

删除操作：

parent.right = cur.right;

1.3 cur不是根结点，cur是parent的左子树
（cur != root && cur == parent.left）

删除操作：

parent.left = cur.right;

2.cur的右子树为空（cur.right == null）
2.1 cur是根结点 （cur == root）

删除操作：

root = cur.left;

2.2 cur不是根结点，cur是parent的右子树
（cur != root && cur == parent.right）

删除操作：

parent.right = cur.left;

2.3 cur不是根结点，cur是parent的左子树
（cur != root && cur == parent.left）

删除操作：

parent.left = cur.left;

3.cur的左右子树都不为空
删除步骤：下面两个选择一个
（1）在左子树中找到最大值的结点，用该结点的值于cur的值进行交换，之后将最大值结点从它的父结点上删除
（2）在右子树中找到最小值的结点，用该结点的值于cur的值进行交换，之后将最小值结点从它的父结点上删除

用（2）举例子：
goat为最值结点（最小值结点）
parenr为goat的父结点

删除操作：

if (goat == parent.left) {
    parent.left = goat.right;
} else {
    parent.right = goat.right;
}

具体删除函数

public void remove(int key) {
        BinarySearchNode<V> cur = root;
        BinarySearchNode<V> parent = null;
        while (cur != null) {
            if (key < cur.key) {
                parent = cur;
                cur = cur.leftNode;
            } else if (key > cur.key) {
                parent = cur;
                cur = cur.rightNode;
            } else {
                removeNode(parent, cur);
                return;
            }
        }
    }

    private void removeNode(BinarySearchNode<V> parent, BinarySearchNode<V> cur) {
        if (cur.leftNode == null) {
            if (cur == root) {
                root = cur.rightNode;
            } else if (cur != root) {
                parent.rightNode = cur.rightNode;
            } else {
                parent.leftNode = cur.rightNode;
            }
        } else if (cur.rightNode == null) {
            if (cur == root) {
                root = cur.leftNode;
            } else if (cur != root) {
                parent.rightNode = cur.leftNode;
            } else {
                parent.leftNode = cur.leftNode;
            }
        } else {
            BinarySearchNode<V> goat = cur;
            BinarySearchNode<V> goatParent = parent;
            while (goat.leftNode != null) {
                goatParent = goat;
                goat = goat.leftNode;
            }
            cur.key = goat.key;
            cur.value = goat.value;
            if (goat == goatParent.leftNode) {
                goatParent.leftNode = goat.rightNode;
            } else {
                goatParent.rightNode = goat.rightNode;
            }
        }
}