模拟实现【二叉搜索树】

✨hello，愿意点进来的小伙伴们，你们好呐！
✨ 🐻🐻系列专栏：【数据结构】
🐲🐲本篇内容： 【二叉搜索树的模拟实现】
🐯🐯作者简介:一名现大二的三非编程小白

二叉搜索树介绍

二叉搜索树是一颗很特殊的二叉树：
作为TreeMap的底层基础实现究竟是怎么样的呢？
1. 它的左节点不为空的时候，则该节点的左子树上的所有结点值都小于该节点。
2. 若它的右节点不为null，则该节点的右子树上的所有节点值都大于该节点值。
3. 它的左右子树也是按照该规则来建立的。

如图所示：

接下来我们自己来实现一下二叉搜索树 的主要操作，加深对二叉搜索树的理解。

二叉搜索树实现：

1. 定义静态内部类 TreeNode

static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }
1
2
3
4
5
6
7
8
9

2. 操作 – 查找

/**
     * 在二叉搜索树中搜索val节点
     * @param val
     * @return
     */
    public TreeNode search(int val){
        TreeNode cur = root;
        while(cur != null){
            if(val > cur.val){
                cur = cur.right;
            }else if (val < cur.val){
                cur = cur.left;
            }else{
                //找到该节点
                return cur;
            }
        }
        //没有找到节点就返回null
        return null;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3. 操作 – 插入

 /**
     * 在二叉搜索树中插入key
     * @param key
     * @return
     */
    public boolean insert(int key){
        //如果该树为null
        if(root == null){
            root = new TreeNode(key);
            return true;
        }

        //不为null
        TreeNode cur = root;
        TreeNode curPrev = null;
        while(cur != null){
            if(key > cur.val){
                curPrev = cur;
                cur = cur.right;
            }else if (key < cur.val){
                curPrev = cur;
                cur = cur.left;
            }else {
                //当二叉搜索树中有
                return false;
            }
        }
        //判断该插入curPrev节点的左或者右
        TreeNode node = new TreeNode(key);
        if(curPrev.right == cur){
            curPrev.right = node;
        }else{
            curPrev.left = node;
        }
        return true;
    }

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

4. 操作 – 删除

 /**
     * 在二叉搜索树中删除元素
     * @param key
     */
    public void remove(int key){
        TreeNode cur = root;

        TreeNode curParent = null;
        while(cur != null){
            if(key > cur.val){
                curParent = cur;
                cur = cur.right;
            }else if (key < cur.val){
                curParent = cur;
                cur = cur.left;
            }else{
                removeNode(curParent,cur);
                return;
            }
        }
    }

    public void removeNode(TreeNode curParent,TreeNode cur){
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if (curParent.right == cur){
                curParent.right = cur.right;
            }else{
                curParent.left = cur.right;
            }
        }else if (cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if (curParent.right == cur){
                curParent.right = cur.left;
            }else{
                curParent.left = cur.left;
            }
        }else{
            //cur左右都有节点
            //找替罪羊
            TreeNode next = cur.right;
            TreeNode nextParent = cur;

            //找到cur.right.left的末节点
            while(next.left != null){
                nextParent = next;
                next = next.left;
            }
            //找到替罪羊节点
            cur.val = next.val;
            if(nextParent.left == next){
                nextParent.left = next.right;
            }else{
                //处理的是cur.right.left为null的情况
                nextParent.right = next.right;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

Java代码集合：

/**
 * @author 罗鸿基
 * @version 1.0
 */
public class MyNewBinarySearchTree {
    //使用静态内部类类定义TreeNode
    static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int val) {
            this.val = val;
        }
    }

    public TreeNode root = null;

    /**
     * 在二叉搜索树中搜索val节点
     * @param val
     * @return
     */
    public TreeNode search(int val){
        TreeNode cur = root;
        while(cur != null){
            if(val > cur.val){
                cur = cur.right;
            }else if (val < cur.val){
                cur = cur.left;
            }else{
                //找到该节点
                return cur;
            }
        }
        //没有找到节点就返回null
        return null;
    }

    /**
     * 在二叉搜索树中插入key
     * @param key
     * @return
     */
    public boolean insert(int key){
        //如果该树为null
        if(root == null){
            root = new TreeNode(key);
            return true;
        }

        //不为null
        TreeNode cur = root;
        TreeNode curPrev = null;
        while(cur != null){
            if(key > cur.val){
                curPrev = cur;
                cur = cur.right;
            }else if (key < cur.val){
                curPrev = cur;
                cur = cur.left;
            }else {
                //当二叉搜索树中有
                return false;
            }
        }
        //判断该插入curPrev节点的左或者右
        TreeNode node = new TreeNode(key);
        if(curPrev.right == cur){
            curPrev.right = node;
        }else{
            curPrev.left = node;
        }
        return true;
    }

    /**
     * 在二叉搜索树中删除元素
     * @param key
     */
    public void remove(int key){
        TreeNode cur = root;

        TreeNode curParent = null;
        while(cur != null){
            if(key > cur.val){
                curParent = cur;
                cur = cur.right;
            }else if (key < cur.val){
                curParent = cur;
                cur = cur.left;
            }else{
                removeNode(curParent,cur);
                return;
            }
        }
    }

    public void removeNode(TreeNode curParent,TreeNode cur){
        if(cur.left == null){
            if(cur == root){
                root = cur.right;
            }else if (curParent.right == cur){
                curParent.right = cur.right;
            }else{
                curParent.left = cur.right;
            }
        }else if (cur.right == null){
            if(cur == root){
                root = cur.left;
            }else if (curParent.right == cur){
                curParent.right = cur.left;
            }else{
                curParent.left = cur.left;
            }
        }else{
            //cur左右都有节点
            //找替罪羊
            TreeNode next = cur.right;
            TreeNode nextParent = cur;

            //找到cur.right.left的末节点
            while(next.left != null){
                nextParent = next;
                next = next.left;
            }
            //找到替罪羊节点
            cur.val = next.val;
            if(nextParent.left == next){
                nextParent.left = next.right;
            }else{
                //处理的是cur.right.left为null的情况
                nextParent.right = next.right;
            }
        }
    }

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

分析二叉搜索树：

二叉搜索树在搜查元素的时候，会在每一个根结点进行判断，将会减去一半的元素，这时候一般来说搜查会大幅提高。但是也会有例外，接下来我们来看看它各种情况下的时间复杂度：

1. 完全二叉树

完全二叉树的情况下：
二叉树的搜查效率就会很高，因为每一次都会去除一半的元素。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：logN

2. 单支情况下：

在单分支的情况下，搜索树的搜查效率将会降低，因为每一个都无法去除元素，只能依次遍历下去：
最差情况下，二叉搜索树退化为单支树，其平均比较次数为：N

在这种情况下，二叉搜索树其实就会有一系列的优化手段，比如AVL树，红黑树，这些会在以后的章节介绍到，这一篇实现二叉搜索树的简单方法就结束到这里噢