0%

树结构——二叉查找树

定义

二叉查找树,也称二叉搜索树、有序二叉树(英语:ordered binary tree),排序二叉树(英语:sorted binary tree),是指一棵空树或者具有下列性质的二叉树:

  1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
  • 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
  • 任意节点的左、右子树也分别为二叉查找树;
  • 没有键值相等的节点。 删除一个有左、右子树的节点
    先弄出一个二叉树的叶子
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    private static class BinaryNode<K,V> {
    K key; // 键
    V value; // 值
    BinaryNode<K,V> left; // 左子树
    BinaryNode<K,V> right; // 右子树

    BinaryNode(K key,V value) {
    this(key,value, null, null);
    }

    BinaryNode(K key,V value, BinaryNode<K,V> left, BinaryNode<K,V> right) {
    this.key = key;
    this.value = value;
    this.left = left;
    this.right = right;
    }
    }

插入算法

向一个二元搜寻树b中插入一个节点s的算法,过程为:

  1. 若b是空树,则将s所指结点作为根节点插入,否则:
  • 若s->data等于b的根节点的数据域之值,则返回,否则:
  • 若s->data小于b的根节点的数据域之值,则把s所指节点插入到左子树中,否则:
  • 把s所指节点插入到右子树中。(新插入节点总是叶子节点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private BinaryNode insert(K key,V value,BinaryNode<K,V> node){
// 如果根为空,则直接把传进来的建值作为树的根
if(node == null){
return new BinaryNode(key,value);
}
// 比较树根和将要成为叶子的值
int result = compare(key,node.key);
// 节点值比根小,将节点插入左子树,否则插入右子树
if(result<0){
node.left = insert(key,value,node.left);
}else if(result > 0){
node.right = insert(key,value,node.right);
}
return node;
}
final int compare(Object k1, Object k2) {
return comparator==null ? ((Comparable<? super K>)k1).compareTo((K)k2)
: comparator.compare((K)k1, (K)k2);
}

查找算法

在二元搜寻树b中查找x的过程为:

  1. 若b是空树,则搜索失败,否则:
  • 若x等于b的根节点的数据域之值,则查找成功;否则:
  • 若x小于b的根节点的数据域之值,则搜索左子树;否则:
  • 查找右子树。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
private BinaryNode<K, V> getEntry(K key) {
if(key == null){
throw new NullPointerException();
}
BinarySearchTree.BinaryNode<K,V> p = rootTree;
while (p != null){
// 比较树根和和传入的key
int cmp = compare(key,p.key);
// 节点值比根小,则查找左子树,否则查找右子树
if(cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}

删除算法

  1. 若*p结点为叶子结点,即PL(左子树)和PR(右子树)均为空树。由于删去叶子结点不破坏整棵树的结构,则只需修改其双亲结点的指针即可。
  • p结点只有左子树PL或右子树PR,此时只要令PL或PR直接成为其双亲结点f的左子树(当p是左子树)或右子树(当p是右子树)即可,作此修改也不破坏二叉查找树的特性。
  • p结点的左子树和右子树均不空。在删去p之后,为保持其它元素之间的相对位置不变,可按中序遍历保持有序进行调整,可以有两种做法:其一是令p的左子树为f的左/右(依p是f的左子树还是右子树而定)子树,s为p左子树的最右下的结点,而p的右子树为s的右子树;其二是令p的直接前驱(in-order predecessor)或直接后继(in-order successor)替代p,然后再从二叉查找树中删去它的直接前驱(或直接后继)。
    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
    private BinaryNode<K, V> deleteEntry(K key, BinaryNode<K, V> node) {
    if (node == null) {
    return node;
    }
    int result = compare(key, node.key);
    if (result < 0) {
    // 存在左子树
    node.left = deleteEntry(key, node.left);
    } else if (result > 0) {
    // 存在右子树
    node.right = deleteEntry(key, node.right);
    } else if (node.left != null && node.right != null) {
    /**
    * 这边删除可以有两种方式,一种是找到右子树的最左节点,还有一种是找到左子树的最右节点
    * 然后把要删除的节点替换掉
    * node.key = findMax(node.left).key;
    * node.value = findMax(node.left).value;
    * node.left = deleteEntry(node.key, node.left);
    */
    // 找到右子树的左边最小节点把要删除的节点替换掉
    node.key = findMin(node.right).key;
    node.value = findMin(node.right).value;
    // 替换掉之后将节点删除
    node.right = deleteEntry(node.key, node.right);
    } else
    node = (node.left != null) ? node.left : node.right;
    return node;

    }

二叉查找树的弊端

最坏情况下,当先后插入的关键字有序时,构成的二叉查找树蜕变为单支树,这个时候复杂度会退化成O(n)

完整代码

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
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
/**
* Created by tianzeng on 2017/5/13.
* 二叉查找树
* 1. 若任意节点的左子树不空,则左子树上所有结点的值均小于它的根结点的值;
* 2. 若任意节点的右子树不空,则右子树上所有结点的值均大于它的根结点的值;
* 3. 任意节点的左、右子树也分别为二叉查找树;
* 4. 没有键值相等的节点
*/

public class BinarySearchTree<K, V> {
/**
* 节点的数据结构
*/
private static class BinaryNode<K, V> {
K key;
V value;
BinaryNode<K, V> left;
BinaryNode<K, V> right;

BinaryNode(K key, V value) {
this(key, value, null, null);
}

BinaryNode(K key, V value, BinaryNode<K, V> left, BinaryNode<K, V> right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}

private BinaryNode rootTree; //
private final Comparator<? super K> comparator;

/**
* 构造一个空的二叉查找树
*/
public BinarySearchTree() {
this.comparator = null;
rootTree = null;
}
public BinarySearchTree(Comparator<? super K> comparator) {
this.comparator = comparator;
}
/**
* 清空二叉查找树
*/
public void clear() {
rootTree = null;
}

/**
* 判断二叉树是否为空
*/
public boolean isEmpty() {
return rootTree == null;
}

final int compare(Object k1, Object k2) {
return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2)
: comparator.compare((K) k1, (K) k2);
}

/**
* 插入元素
*/
public void put(K key, V value) {
rootTree = insert(key, value, rootTree);
}

/**
* 插入元素
*/
private BinaryNode insert(K key, V value, BinaryNode<K, V> node) {
// 如果根为空
if (node == null) {
return new BinaryNode(key, value);
}
int result = compare(key, node.key);
// 节点值比根小,左子树
if (result < 0) {
node.left = insert(key, value, node.left);
} else if (result > 0) {
node.right = insert(key, value, node.right);
}
return node;
}

/**
* 查找元素
*/
public V get(K key) {
BinarySearchTree.BinaryNode<K, V> p = getEntry(key);
return (p == null ? null : p.value);
}

private BinaryNode<K, V> getEntry(K key) {
if (key == null) {
throw new NullPointerException();
}
BinarySearchTree.BinaryNode<K, V> p = rootTree;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}

public void remove(K key) {
rootTree = deleteEntry(key, rootTree);
}

/**
* 寻找该节点的最小节点
*/
BinaryNode<K,V> findMin(BinaryNode<K, V> node){
if(node == null){
return null;
}else if(node.left == null){
return node;
}
return findMin(node.left);
}
BinaryNode<K,V> findMax(BinaryNode<K, V> node){
if(node == null){
return null;
}else if(node.right == null){
return node;
}
return findMax(node.right);
}
private BinaryNode<K, V> deleteEntry(K key, BinaryNode<K, V> node) {
if (node == null) {
return node;
}
int result = compare(key, node.key);
if (result < 0) {
// 存在左子树
node.left = deleteEntry(key, node.left);
} else if (result > 0) {
// 存在右子树
node.right = deleteEntry(key, node.right);
} else if (node.left != null && node.right != null) {
/**
* node.key = findMax(node.left).key;
* node.value = findMax(node.left).value;
* node.left = deleteEntry(node.key, node.left);
*/
// 找到右子树的左边最小节点把要删除的节点替换掉
node.key = findMin(node.right).key;
node.value = findMin(node.right).value;
// 替换掉之后将节点删除
node.right = deleteEntry(node.key, node.right);
} else
node = (node.left != null) ? node.left : node.right;
return node;

}
public void print(){
print(rootTree);
}

public void print(BinaryNode root) {
if (root == null) {
return;
}

List<BinaryNode> list = new LinkedList<>();
BinaryNode node;
// 当前层的结点个数
int current = 1;
// 记录下一层的结点个数
int next = 0;
list.add(root);

while (list.size() > 0) {
node = list.remove(0);
current--;
System.out.printf("%-3s", node.value);

if (node.left != null) {
list.add(node.left);
next++;
}
if (node.right != null) {
list.add(node.right);
next++;
}

if (current ==0) {
System.out.println();
current = next;
next = 0;
}
}
}
}

测试:

参考资料

维基百科——二叉搜索树
二叉树(BST树)内结点的删除
6天通吃树结构—— 第一天 二叉查找树