關(guān)于二叉樹中的點到底用“節(jié)點”還是“結(jié)點”。節(jié)點被認(rèn)為是一個有處理能力的實體，比如網(wǎng)絡(luò)上的一臺計算機(jī)；而結(jié)點則只是一個交叉點，像“結(jié)繩記事”，打個結(jié)做個標(biāo)記，僅此而已。還有就是，要記?。?strong>一般算法中點的都是結(jié)點。
二叉搜索樹支持多種操作，包括Search、Minimum、Maximum、Predecessor、Successor、Insert和Delete等操作，且其基本操作所花費的時間與這棵樹的高度成正比。
完全二叉樹的最壞運(yùn)行時間為：，樹如果由
個節(jié)點的組成的線性鏈，則最好運(yùn)行時間為：
。
二叉搜索樹的定義
二叉搜索樹又稱為做二叉排序樹、二叉查找樹。其要么是一課空樹，要么是一個滿足以下性質(zhì)的二叉樹：
- 若它的左子樹不空，則左子樹上所有節(jié)點的關(guān)鍵字均小于根節(jié)點關(guān)鍵字
- 若它的右子樹不空，則右子樹上所有節(jié)點的關(guān)鍵字均大于根節(jié)點關(guān)鍵字
- 它的左右子樹依舊是二叉搜索樹
- 沒右關(guān)鍵字相等的節(jié)點
算法導(dǎo)論中指出，左右子樹均可以包含和根節(jié)點大小相等的元素
二叉搜索樹具有的特點：
- 按中序遍歷二叉搜索樹所得的中序序列是一個遞增的有序序列。
- 統(tǒng)一個數(shù)據(jù)集合可構(gòu)造的二叉搜索樹不唯一，但中序序列相同。
Search
二叉搜索樹在搜索某個關(guān)鍵字遇到節(jié)點x時，將關(guān)鍵字k與x.key比較：
- 如果
k==x.key，查找終止并返回x。 - 如果
k<x.key，繼續(xù)在x的左子樹中查找，如果左子樹為空則返回null。 - 如果
k>x.key，繼續(xù)在x的右子樹中查找，如果左子樹為空則返回null。
上述過程所需的運(yùn)行時間為，其中
表示樹的高度。其代碼為：
public TreeNode search(TreeNode node, int key) {
while (node != null) {
if (node.val == key) return node;
else if (node.val > key) node = node.left;
else node = node.right;
}
return node;
}
Minimum
二叉搜索樹從根節(jié)點沿著左孩子的指針直到遇到null，并返回左孩子指針為null的節(jié)點。
上述過程所需的運(yùn)行時間為，其中
表示樹的高度。其代碼為：
public TreeNode minimum(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
Maximum
二叉搜索樹從根節(jié)點沿著右孩子的指針直到遇到null，并返回右孩子指針為null的節(jié)點。
上述過程所需的運(yùn)行時間為，其中
表示樹的高度。其代碼為：
public TreeNode maximum(TreeNode node) {
while (node.right != null) node = node.right;
return node;
}
Successor
二叉搜索樹尋找后繼分為兩種情況：
- 節(jié)點
x的右子樹非空，那么x的后繼就是x右子樹的最左節(jié)點（右子樹中最小的節(jié)點）。 - 節(jié)點
x的右子樹為空，那么簡單地從x沿著樹向上搜索，直到搜索到當(dāng)前根節(jié)點是父節(jié)點的左子樹的根為止，此時該父節(jié)點是x的后繼。
上述過程所需的運(yùn)行時間為，其中
表示樹的高度。其代碼為：
public TreeNode successor(TreeNode node) {
if (node.right != null) return minimum(node.right);
while (node.p != null && node == node.p.right) node = node.p;
return node.p;
}
Predecessor
二叉搜索樹尋找前驅(qū)分為兩種情況：
- 節(jié)點
x的左子樹非空，那么x的前驅(qū)就是x左子樹的最右節(jié)點（左子樹中最大的節(jié)點）。 - 節(jié)點
x的右子樹為空，那么簡單地從x沿著樹向上搜索，直到搜索到當(dāng)前根節(jié)點是父節(jié)點的右子樹的根為止，此時該父節(jié)點是x的前驅(qū)
上述過程所需的運(yùn)行時間為，其中
表示樹的高度。其代碼為：
public TreeNode predecessor(TreeNode node) {
if (node.left != null) return maximum(node.left);
while (node.p != null && node == node.p.left) node = node.p;
return node.p;
}
Insert
插入節(jié)點之后仍要滿足二叉搜索樹的特性。如果要插入的值為z，二叉搜索樹在節(jié)點x處的處理情況分為兩種：
- 如果當(dāng)前節(jié)點為空，直接將
z值插入； - 如果當(dāng)前節(jié)點不空：
- 如果
z<x.key，繼續(xù)在x的左子樹中插入 - 如果
z>x.key，繼續(xù)在x的右子樹中插入
- 如果
其代碼為：
public TreeNode insert(TreeNode root, int z) {
if (root == null) {
root = new TreeNode(z);
return root;
}
TreeNode node = root;
while (true) {
if (z < node.val) {
if (node.left == null) {
node.left = new TreeNode(z);
node.left.p = node;
break;
}
node = node.left;
}
if (z > node.val) {
if (node.right == null) {
node.right = new TreeNode(z);
node.right.p = node;
break;
}
node = node.right;
}
}
return root;
}
Delete
刪除節(jié)點之后仍要滿足二叉搜索樹的特性。在二叉搜索樹T中刪除一個節(jié)點z分為三種情況：
- 如果節(jié)點
z沒有孩子節(jié)點，則直接刪除該節(jié)點 - 如果節(jié)點
z只有左子樹或者右子樹中的一個，則直接繼承：將該子樹移到被刪除節(jié)點的位置 - 如果節(jié)點
z擁有兩個子樹，則用后繼或者先驅(qū)節(jié)點取代被刪除的節(jié)點。
其代碼為：
public TreeNode delete(TreeNode node, int x) {
TreeNode root = node;
while (node != null) {
if (node.val == x) {
if (node.left != null && node.right != null) { // 情況 3
TreeNode maximum = maximum(node.left);
node.val = maximum.val;
if (maximum.p.left != null && maximum.p.left.val == maximum.val) maximum.p.left = maximum.left;
if (maximum.p.right != null && maximum.p.right.val == maximum.val) maximum.p.right = null;
} else if (node.left == null && node.right == null) { // 情況 1
if (node.p.left != null && node.p.left.val == x) node.p.left = null;
if (node.p.right != null && node.p.right.val == x) node.p.right = null;
} else { // 情況 2
if (node.left != null) {
node.val = node.left.val;
node.right = node.left.right;
if (node.left.left != null) node.left.left.p = node;
if (node.left.right != null) node.left.right.p = node;
node.left = node.left.left;
} else if (node.right != null) {
node.val = node.right.val;
node.left = node.right.left;
if (node.right.left != null) node.right.left.p = node;
if (node.right.right != null) node.right.right.p = node;
node.right = node.right.right;
}
}
break;
}
if (node.val > x && node.left != null) node = node.left;
if (node.val < x && node.right != null) node = node.right;
}
return root;
}
算法導(dǎo)論第三版中給出了構(gòu)建深度接近
的隨機(jī)構(gòu)建二叉搜索樹，按照隨機(jī)的次序插入關(guān)鍵字到一顆空樹中。為降低樹的高度還出現(xiàn)了各種“平衡"搜索樹。
完整代碼：
package org.example;
public class Template {
public TreeNode search(TreeNode node, int key) {
while (node != null) {
if (node.val == key) return node;
else if (node.val > key) node = node.left;
else node = node.right;
}
return node;
}
public TreeNode minimum(TreeNode node) {
while (node.left != null) node = node.left;
return node;
}
public TreeNode maximum(TreeNode node) {
while (node.right != null) node = node.right;
return node;
}
public TreeNode successor(TreeNode node) {
if (node.right != null) return minimum(node.right);
while (node.p != null && node == node.p.right) node = node.p;
return node.p;
}
public TreeNode predecessor(TreeNode node) {
if (node.left != null) return maximum(node.left);
while (node.p != null && node == node.p.left) node = node.p;
return node.p;
}
public TreeNode insert(TreeNode root, int z) {
if (root == null) {
root = new TreeNode(z);
return root;
}
TreeNode node = root;
while (true) {
if (z < node.val) {
if (node.left == null) {
node.left = new TreeNode(z);
node.left.p = node;
break;
}
node = node.left;
}
if (z > node.val) {
if (node.right == null) {
node.right = new TreeNode(z);
node.right.p = node;
break;
}
node = node.right;
}
}
return root;
}
public TreeNode delete(TreeNode node, int x) {
TreeNode root = node;
while (node != null) {
if (node.val == x) {
if (node.left != null && node.right != null) {
TreeNode maximum = maximum(node.left);
node.val = maximum.val;
if (maximum.p.left != null && maximum.p.left.val == maximum.val) maximum.p.left = maximum.left;
if (maximum.p.right != null && maximum.p.right.val == maximum.val) maximum.p.right = null;
} else if (node.left == null && node.right == null) {
if (node.p.left != null && node.p.left.val == x) node.p.left = null;
if (node.p.right != null && node.p.right.val == x) node.p.right = null;
} else {
if (node.left != null) {
node.val = node.left.val;
node.right = node.left.right;
if (node.left.left != null) node.left.left.p = node;
if (node.left.right != null) node.left.right.p = node;
node.left = node.left.left;
} else if (node.right != null) {
node.val = node.right.val;
node.left = node.right.left;
if (node.right.left != null) node.right.left.p = node;
if (node.right.right != null) node.right.right.p = node;
node.right = node.right.right;
}
}
break;
}
if (node.val > x && node.left != null) node = node.left;
if (node.val < x && node.right != null) node = node.right;
}
return root;
}
public static void main(String[] args) {
Template template = new Template();
TreeNode left = new Template().new TreeNode(3);
TreeNode right = new Template().new TreeNode(6);
TreeNode root = new Template().new TreeNode(4, left, right);
left.p = root;
right.p = root;
System.out.println(template.search(root, 5));
System.out.println(template.minimum(root).val);
System.out.println(template.maximum(root).val);
TreeNode successor = template.successor(root);
System.out.println(successor == null ? null : successor.val);
TreeNode predecessor = template.predecessor(right);
System.out.println(predecessor == null ? null : predecessor.val);
TreeNode node = template.insert(root, 1);
System.out.println(node.left.left.p.val);
TreeNode node2 = template.insert(root, 0);
TreeNode node3 = template.insert(root, 2);
TreeNode node1 = template.delete(root, 1);
System.out.println(node1.left.left.right.val);
}
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode p;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
}
題目鏈接
參考文獻(xiàn)：
- 二叉搜索樹
- 二叉搜索樹及其操作詳解
- Thomas,H.Cormen,Charles,E.Leiserson,Ronald,L.Rivest,Clifford,Stein,殷建平,徐云,王剛,劉曉光,蘇明,鄒恒明,王宏志. 算法導(dǎo)論(原書第3版)[J]. 計算機(jī)教育, 2013(10):1.
