二叉搜索树

作者：~小明学编程 

文章专栏：Java数据结构

格言：目之所及皆为回忆，心之所想皆为过往

目录

什么是二叉搜索树

二叉搜索树的操作

二叉搜索树的节点

插入操作(insert)

代码

搜索(search)

代码

删除操作(remove)

代码

性能分析

---

什么是二叉搜索树

所谓二叉搜索树其实就是二叉树的一种，也叫做二叉排序树，在二叉搜索树中：

当它的左树不是空的时候，其左树中的所有节点的值都小于根节点，

当它的右树不是空的时候，其右树中的所有节点的值都大于根节点，

同时其左右树也是二叉搜索树。

如图：

二叉搜索树的操作

二叉搜索树的节点

class NodeTree {
    public int val;
    public NodeTree left;
    public NodeTree right;
    public NodeTree(int val) {
        this.val = val;
    }
}

这是我们所构建的二叉搜索树的节点，其中包括我们的值val,左子树的地址，右子树的节点。

插入操作(insert)

1.在我们第一次向二叉树中插入数据的时候肯定是一个空树，所以我们要进行一个判断如果我们的根节点root为空的话我们就new一个节点然后将该节点当作我们的根节点。

2.因为我们的二叉树是有序的所以我们在遍历二叉搜索树的时候也比较方便，通过对val的比较来选择我们向我们的左子树进行遍历还是向我们的右子树进行遍历。

3.假设我们的key是我们要进行插入的数据，现在我们进行遍历，如果我们的当前节点的val小于key的话那么就向右遍历，否则就向左遍历。

 直到我们搜索到空节点，

 那么问题来了我们的cur已经是空节点了，那么我们该怎么进行插入呢？

4.我们可以设置一个父节点，父节点存储着我们的上一个节点的位置，这样我们就能进行插入了。

 然后再次将parent的val与key进行比较，选择插在左还是插在右边。

注意：

我们的二叉搜索树中是不能有重复的树的，所以当我们遇到重复元素的时候就直接返回false，意味着我们插入失败。

代码

    //插入操作
    public boolean insert(int key) {
        NodeTree cur = root;
        NodeTree parent = cur;
        if (root==null) {
            root = new NodeTree(key);
            return true;
        }
        while (cur!=null) {
            if (cur.val==key) {
                return false;
            } else if (cur.val
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        //找到之后开始放入节点
        NodeTree nodeTree = new NodeTree(key);
        if (parent.val
            parent.right = nodeTree;
        } else {
            parent.left = nodeTree;
        }
        return true;
    }

搜索(search)

在了解了插入操作之后我们的搜索操作就比较简单了，就是当前节点与我们的key进行比较当，valkey的时候就向左遍历，当val==key的时候直接返回当前的节点,当遍历完整个搜索树依然没有找到的话就返回false。

代码

    //搜索操作
    public NodeTree search(int key) {
        NodeTree cur = root;
        while (cur !=null) {
            if (cur.val==key) {
                return cur;
            } else if (cur.val
                cur = cur.right;
            } else {
                cur = cur.left;
            }
        }
        return null;
    }

删除操作(remove)

删除操作相对而言就比较的麻烦了，我们要分很多情况考虑。

一丶我们既然想要删除，那么就必须要进行搜索和重新的连接，也就是说前面的代码是和search差不多，并且需要parent进行重新的插入。

二丶对二叉树进行遍历并且找到我们要要删除的val节点，找到之后进行删除。

三丶

设我们当前待删除的节点为cur,待删除节点的父节点为parent。

1.cur.left==null

(1)当我们的待删除节点为根节点的时候

 我们的root=root.right。

（2）当cur==parent.left时

 可以看到此时我们parent.left=cur.right。

(3)当cur==parent.right的时候

 由图可见此时parent.right = cur.right。

2.cur.right==null

(1)当我们的cur==root的时候

 此时root = cur.left。

(2)当cur==parent.left时

 此时parent.left = cur.left。

(3)当cur==parent.right时

此时parent.right = cur.left。

3.cur.left!=null&&cur.right!=null

此时我们要用替换法将我们想要删除的节点重新进行赋值，赋值为其右边最小的节点，

此时我们就要遍历其右子树找出其最小的节点，也就是遍历右树的最左节点，我们将其称为target,其父节点为targetParent。

（1）target==targetParent.left

 此时targetParent.left = target.right。

（2）target==targetParent.right

 此时targetParent.right = target.right。

代码

    public boolean remove(int key) {
        NodeTree cur = root;
        NodeTree parent = cur;
        while (cur!=null) {
            if (cur.val==key) {
                removeNode(cur,parent);
                return true;
            } else if (cur.val
                parent = cur;
                cur = cur.right;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        return false;
    }
    private void removeNode(NodeTree cur,NodeTree parent) {
        if (cur.left==null) {
            if (cur==root) {
                root = cur.right;
            } else if (cur==parent.left) {
                parent.left = cur.right;
            } else if (cur==parent.right) {
                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 if (cur==parent.right) {
                parent.right = cur.left;
            }
        } else {
            NodeTree targetParent = cur;
            NodeTree target = cur.right;
            while (target.left!=null) {
                targetParent = target;
                target = target.left;
            }
            cur.val = target.val;
            if (target == targetParent.left) {
                targetParent.left = target.right;
            } else {
                targetParent.right = target.right;
            }
        }
    }

性能分析

我们二叉搜索树类似二叉树，在我们的平衡的状态下，其平均比较的次数就是二叉树的深度，也就是log(N)，最差情况下也就是形成一个单链表的情况，其平均比较次数为2/N，那么我们能不能让其无论在什么情况下都近似为一棵平衡的树呢，当然可以，这就是我们的红黑树，在后面我们将会介绍。

今天的二叉搜索树就介绍到这里如果觉得有帮助的话那就点个赞吧，感谢大家的支持。