1.二叉搜索树的概念

二叉搜索树是一颗特殊的二叉树:

它的左子树的所有节点的值,均小于根节点;

它的右子树的所有节点的值,均大于根节点.

二叉搜索树的中序遍历总是有序的!!!

二叉搜索树查找数据的时间复杂度为 O(logN) ,当树为单分支树时,时间复杂度达到 O(N) .

2.二叉搜索树的实现

2.1 定义节点类

    static class TreeNode {
        public int key;
        public TreeNode left;
        public TreeNode right;
 
        TreeNode(int key) {
            this.key = key;
        }
    }

2.2 查找

根据二叉搜索树的性质,查找一个数据不需要用常规的遍历方法去遍历二叉树的所有节点.

我们可以根据根节点与要查找的数据的大小比较,判断要找的数据在左子树还是右子树

//查找key是否存在
    public TreeNode search(int key) {
        TreeNode cur = root;
        while(cur != null) {
            if(cur.key == key) {
                return cur;
            } else if(cur.key > key) {
                cur = cur.left;
            } else {
                cur = cur.right;
            }
        }
        return null;
    }

2.3 插入

有了上面查找的思路,插入就不难,所以按照搜索的思路,当找到null的时候将节点放在空位置就好了,但是在二叉搜索树中没有相同的节点,所以当有相等的节点出现要放弃插入

    public boolean insert(int key) {
        if(root == null) {
            root = new TreeNode(key);
            return true;
        }
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.key == key) {
                return false;
            } else if(cur.key < key) {
                prev = cur;
                cur = cur.right;
            } else {
                prev = cur;
                cur = cur.left;
            }
        }
        TreeNode node = new TreeNode(key);
        if(prev.key > key) {
            prev.left = node;
        } else {
            prev.right = node;
        }
        return true;
    }

2.4 删除

删除数据仍然要找到要删除的节点,并且要修改节点的引用,所以我们需要一个变量去得到要删除节点的双亲节点

下面是寻找节点,删除的操作在removeNode()方法中

    //删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.key == key) {
                removeNode(cur,prev);
                return true;
            } else if(cur.key > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }
        return false;
    }

有了要删除的节点的位置以及它的双亲节点,那么接下来就是删除操作

删除可以分为上情况:

1.要删除的节点 没有左子树

2.要删除的节点 没有右子树

3.要删除的节点 既有左子树 还有右子树

1和2又各自可以分为三种情况:

(1) 要删除的节点是根节点

(2) 要删除的节点是双亲节点的左孩子

(3) 要删除的节点是双亲节点的右孩子

根据上述情况可以得到下面的代码

public void removeNode(TreeNode cur,TreeNode parent) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            } else if(cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            } else if(cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        }
    }

接下来是第三种情况

如果该节点的左右子树都存在,那么根节点的替代节点就要大于左子树的所有节点,又不能大于右子树中的任意一个节点,这两个条件全部满足就只有右子树中的最小的节点

那么现在问题就变成了如何找到右子树最小的节点

首先定义两个节点变量,一个指向要删除的节点,一个指向该节点的右孩子,然后控制这两个变量去寻找最小节点

找点节点后,将该节点的值,赋值给要删除的节点

然后将找到的最小的节点给删除掉

接下来又分为两种情况:

1.删除节点的右节点没有左孩子

2.有左孩子

如果没有左孩子那么值需要再将要删除节点的右孩子更改为它右孩子的右孩子即可

如果有左孩子,那么就可以将问题转变成删除没有左孩子的节点(可以参考前面代码)

            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            if(targetParent.right == target) {
                targetParent.right = target.right;
            } else {
                targetParent.left = target.right;
            }

下面是删除操作的全部代码

//删除key的值
    public boolean remove(int key) {
        TreeNode cur = root;
        TreeNode prev = null;
        while(cur != null) {
            if(cur.key == key) {
                removeNode(cur,prev);
                return true;
            } else if(cur.key > key) {
                prev = cur;
                cur = cur.left;
            } else {
                prev = cur;
                cur = cur.right;
            }
        }
        return false;
    }

    public void removeNode(TreeNode cur,TreeNode parent) {
        if(cur.left == null) {
            if(cur == root) {
                root = cur.right;
            } else if(cur == parent.left) {
                parent.left = cur.right;
            } else {
                parent.right = cur.right;
            }
        } else if(cur.right == null) {
            if(cur == root) {
                root = cur.left;
            } else if(cur == parent.left) {
                parent.left = cur.left;
            } else {
                parent.right = cur.left;
            }
        } else {
            TreeNode targetParent = cur;
            TreeNode target = cur.right;
            while(target.left != null) {
                targetParent = target;
                target = target.left;
            }
            cur.key = target.key;
            if(targetParent.right == target) {
                targetParent.right = target.right;
            } else {
                targetParent.left = target.right;
            }
        }
    }