二叉搜索树，常用操作包括

  1. search
  2. maximum
  3. minimum
  4. successor
  5. predecessor
  6. insert
  7. delete

在这里把常用操作的代码总结一下：

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
140
public class BinarySearchTree {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode parent;
        TreeNode(int x) {
            val = x;
        }
    }
    public class Tree {
        TreeNode root;
        public Tree(TreeNode root) {
            this.root = root;
        }
    }
    public TreeNode search(TreeNode x, int k) {
        if (x == null || x.val == k)
            return x;
        if (k < x.val) {
            return search(x.left, k);
        }
        return search(x.right, k);
    }
    public TreeNode iterativeSearch(TreeNode x, int k) {
        while (x != null && x.val != k) {
            if (k < x.val)
                x = x.left;
            else
                x = x.right;
        }
        return x;
    }
    public TreeNode minimum(TreeNode x) {
        if (x == null)
            return x;
        while (x.left != null) {
            x = x.left;
        }
        return x;
    }
    public TreeNode maximum(TreeNode x) {
        if (x == null)
            return x;
        while (x.right != null) {
            x = x.right;
        }
        return x;
    }
    public TreeNode successor(TreeNode x) {
        if (x == null)
            return x;
        while (x.right != null)
            return minimum(x.right);
        TreeNode p = x.parent;
        while (p != null && x == p.right) {
            x = p;
            p = p.parent;
        }
        return p;
    }
    public TreeNode predecessor(TreeNode x) {
        if (x == null)
            return x;
        while (x.left != null)
            return maximum(x.left);
        TreeNode p = x.parent;
        while (p != null && x == p.left) {
            x = p;
            p = p.parent;
        }
        return p;
    }
    public void insert(Tree t, TreeNode z) {
        TreeNode p = null, x = t.root;
        while (x != null) {
            p = x;
            if (z.val < x.val) {
                x = x.left;
            } else {
                x = x.right;
            }
        }
        z.parent = p;
        if (p == null) {
            t.root = z; // tree is empty
        } else if (z.val < p.val) {
            p.left = z;
        } else {
            p.right = z;
        }
    }
    // replace u by v
    private void transplant(Tree t, TreeNode u, TreeNode v) {
        if (u.parent == null)
            t.root = v;
        else if (u == u.parent.left) {
            u.parent.left = v;
        } else
            u.parent.right = v;
        if (v != null)
            v.parent = u.parent;
    }
    public void delete(Tree t, TreeNode z) {
        if (z.left == null) {
            transplant(t, z, z.right);
        } else if (z.right == null) {
            transplant(t, z, z.left);
        } else {
            // 如果z有两个孩子, 那么找z的后继y(一定在z的右子树中), 并让y占据树中z的位置.
            // z的原来右子树部分成为y的新的右子树, 并且z的左子树成主y的新的左子树.
            TreeNode y = minimum(z.right);
            if (y.parent != z) {
                transplant(t, y, y.right);
                y.right = z.right;
                y.right.parent = y;
            }
            transplant(t, z, y);
            y.left = z.left;
            y.left.parent = y;
        }
    }
}