一、什么是二叉查找樹
二叉查找樹是一顆空樹握联,或者是具有一下性質(zhì)的二叉樹:
1.若根結(jié)點的左子樹不為空桦沉,那么左子樹上所有結(jié)點的值都小于根節(jié)點的值
2.若根結(jié)點的右子樹不為空每瞒,那么右子樹上所有結(jié)點的值都小于根節(jié)點的值
3.根節(jié)點的左子樹和右子樹也是二叉查找樹
下圖就是一顆二叉查找樹,每個結(jié)點的值都大于他的左子樹的所有結(jié)點的值永部,每個結(jié)點的值都小于他的右子樹所有結(jié)點的值独泞。
下圖也是一個二叉查找樹,雖然他是一個斜樹苔埋,樹的高度等于結(jié)點的數(shù)量,但是他也符合二叉查找樹的定義(只是搜索的效率很低)蜒犯。
二组橄、二叉查找樹的作用
從名字就可以看出,我們構(gòu)造二叉查找樹的作用是高效地查找罚随、插入和刪除玉工。
2.1 查找
比如,我們在圖一所示的二叉查找樹中查找數(shù)字5是否存在淘菩,查找的步驟如下:
1遵班、5和結(jié)點④比較,5大于4潮改,下一步我們要搜索結(jié)點④的右子樹(根據(jù)二叉查找樹的定義狭郑,一個結(jié)點值小于他的右子樹上所有結(jié)點的值)
2、5和結(jié)點⑥比較汇在,5小于6翰萨,下一步我們要搜索結(jié)點⑥的左子樹
3、5等于結(jié)點5糕殉,查找成功
2.2 插入
我們依然用圖一作為例子亩鬼,這次我們要在圖一所示的二叉樹中插入一個7,步驟如下:
1阿蝶、7和根結(jié)點④比較雳锋,7大于4,下一步搜索右子樹
2羡洁、7和結(jié)點⑥比較玷过,7大于6,下一步搜索右子樹
3焚廊、7和結(jié)點⑧比較冶匹,7小于8,下一步搜索左子樹
4咆瘟、8的左子樹為空嚼隘,那么這里就是7應(yīng)該插入的位置,將7插入到8的左子樹中袒餐。
如下如所示
2.3刪除結(jié)點
刪除結(jié)點比較復(fù)雜飞蛹,我們需要分為四種情況谤狡。
我們以下圖為例來分析這四種情況
2.3.1 待刪除的結(jié)點既沒有左子樹有沒有右子樹
用圖四作為例子,我們需要刪除結(jié)點9卧檐,步驟如下
1墓懂、我們首先要找到結(jié)點9的父節(jié)點8(如果要刪除的結(jié)點沒有父節(jié)點,也就是要刪除的結(jié)點就是根結(jié)點霉囚,那么直接將樹設(shè)置為空樹即可)捕仔。
2、我們將結(jié)點9從其父節(jié)點8的右子樹上刪除盈罐。
2.3.2 待刪除的結(jié)點只有左子樹
用圖四作為例子榜跌,我們要刪除結(jié)點15,它只有左子樹盅粪,刪除的步驟如下
1钓葫、找到待刪除的結(jié)點15
2、將結(jié)點15的左子結(jié)點的值12賦值給結(jié)點15
3票顾、將結(jié)點結(jié)點12的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹
如下圖所示:
2.3.3 待刪除的結(jié)點只有右子樹
用圖四作為例子础浮,我們要刪除結(jié)點5,和2.3.2類似奠骄,步驟如下
1豆同、找到待刪除的結(jié)點5
2、將結(jié)點5的右子結(jié)點的值8賦值給結(jié)點5
3戚揭、將結(jié)點結(jié)點8的左子樹和右子樹分別設(shè)置為待刪除結(jié)點的左子樹和右子樹
2.3.3 待刪除的結(jié)點有左子樹又有右子樹
首先我們應(yīng)該知道诱告,二叉查找樹中序遍歷時結(jié)點的值遞增的(大家可以自己想一下為什么)。
用圖四作為例子民晒,我們要刪除結(jié)點10精居,為了保持二叉查找樹的性質(zhì),我們需要找到中序遍歷中10的左邊一個結(jié)點或者右邊一個結(jié)點來替代10的位置潜必,這里我們選擇中序遍歷中10的左邊一個結(jié)點靴姿。刪除的步驟如下
1、首先找到待刪除的結(jié)點
2磁滚、找到中序遍歷中10的左邊的那個結(jié)點9和該節(jié)點的父節(jié)點8
3佛吓、刪除結(jié)點9
4、將結(jié)點10的值替換為9
如下圖所示
2.4 時間復(fù)雜度分析
當(dāng)二位查找樹是一顆完全二叉樹時垂攘,樹的高度是log(n) + 1维雇,那么查找,插入晒他,刪除的時間復(fù)雜度都是log(n)吱型。
但是如果二叉查找樹不平衡,更機端的情況下變?yōu)橐粋€斜樹陨仅,如圖二所示津滞,那么時間復(fù)雜度就會退化為O(n)铝侵。
三、代碼
這里我使用java來寫二叉查找樹的搜索触徐,插入咪鲜,刪除。其他語言思路一樣撞鹉。
我創(chuàng)建了一個類BinarySearchTree疟丙,類中有一個靜態(tài)內(nèi)部類TreeNode用來表示二叉樹的結(jié)點,類中有一個TreeNode類型成員變量head用來保存二叉查找樹的根節(jié)點鸟雏。
思路在第二章已經(jīng)說明隆敢,這里就不多解釋了。
大家多練練手崔慧,明白其中的原理即可。
package MyBinarySearchTree;
import java.util.Stack;
public class BinarySearchTree {
/**
* 在二叉搜索樹中搜索是否存在指定的結(jié)點穴墅,如果存在指定結(jié)點惶室,返回該結(jié)點,否則返回該結(jié)點在二叉樹中所處位置的父節(jié)點
* @param head
* @param key
* @return
*/
public TreeNode head = null; //根節(jié)點
/**
* 設(shè)置根節(jié)點的值
* @param val
*/
public void setHeadValue(int val) {
if (head == null) {
head = new TreeNode();
head.value = val;
} else {
head.value = val;
}
}
/**
* 在二叉搜索樹中搜索指定結(jié)點
* @param key
* @return
*/
public boolean search(int key) {
TreeNode res = search(head, null, key);
if (res != null && res.value == key) {
return true;
} else {
return false;
}
}
/**
* 輸入根節(jié)點玄货,父節(jié)點皇钞,和要查找的值,找到指定結(jié)點松捉,如果該節(jié)點存在夹界?返回該結(jié)點:否則返回該結(jié)點的父節(jié)點
* @param myHead
* @param father
* @param key
* @return
*/
private TreeNode search(TreeNode myHead, TreeNode father, int key) {
if (myHead == null) {
return father;
} else if (myHead.value == key) {
return myHead;
} else if (myHead.value > key) {
return search(myHead.left, myHead, key);
} else {
return search(myHead.right, myHead, key);
}
}
/**
* 插入結(jié)點,返回結(jié)點引用
* @param head
* @param key
* @return
*/
public TreeNode insert(int key) {
TreeNode res = null;
if (head == null) { //如果樹為空隘世,創(chuàng)建根節(jié)點可柿,返回
head = new TreeNode();
head.value = key;
res = head;
} else {
res = search(head, null, key); //搜索該節(jié)點
if (res.value != key) { //如果二叉搜索樹中不存在該結(jié)點,進行插入
TreeNode newNode = new TreeNode();
newNode.value = key;
if (newNode.value > res.value) {
res.right = newNode;
} else {
res.left = newNode;
}
res = newNode;
}
}
return res;
}
/**
* 刪除指定結(jié)點丙者,如果存在該結(jié)點复斥,返回true,否則返回false
* @param key
* @return
*/
public boolean delete(int key) {
if (head == null) {
return false;
}
TreeNode parent = null;
TreeNode cur = head;
while (cur != null) { //找到要刪除的結(jié)點和其父節(jié)點
if (cur.value == key) {
break;
} else if (cur.value > key){
parent = cur;
cur = cur.left;
} else {
parent = cur;
cur = cur.right;
}
}
if (cur == null) { //如果不存在該結(jié)點,不需要刪除械媒,返回
return false;
} else { //二叉搜索樹中存在該結(jié)點
if (cur.left == null && cur.right == null) { //要刪除的結(jié)點的左右子樹都為空
if (parent == null) { //要刪除的結(jié)點就是根節(jié)點目锭,并且其沒有子結(jié)點,將根節(jié)點設(shè)置為null
head = null;
} else { //從parent中刪除該結(jié)點
if (parent.left == cur) {
parent.left = null;
} else {
parent.right = null;
}
}
} else if (cur.left == null) { //要刪除的結(jié)點的左子樹為空纷捞,要刪除結(jié)點的右結(jié)點頂替
cur.value = cur.right.value;
cur.left = cur.right.left;
cur.right = cur.right.right;
} else if (cur.right == null) { //要刪除的結(jié)點的右子樹為空痢虹,要刪除結(jié)點的左結(jié)點頂替
cur.value = cur.left.value;
cur.right = cur.left.right;
cur.left = cur.left.left;
} else { //要刪除的結(jié)點的所有子樹都不為空,找到中序遍歷的前一個結(jié)點主儡,替換并刪除奖唯。
TreeNode temp = cur;
parent = cur;
cur = cur.left;
while (cur.right != null) {
parent = cur;
cur = cur.right;
}
temp.value = cur.value;
if (parent.left == cur) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
}
return true;
}
}
/**
* 中序遍歷
*/
public void midSearch() {
TreeNode cur = head;
Stack<TreeNode> stack = new Stack<TreeNode>();
while (cur != null || !stack.isEmpty()) {
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
System.out.println(cur.value);
cur = cur.right;
}
}
/**
* 二叉樹結(jié)點
* @author TinyMonster
*
*/
public static class TreeNode {
int value = 0;
TreeNode left = null;
TreeNode right = null;
}
/*
*
*/
public static void main(String[] args) {
BinarySearchTree tree = new BinarySearchTree();
tree.setHeadValue(4);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(6);
tree.insert(5);
tree.insert(7);
tree.midSearch();
System.out.println("-----查找結(jié)點7-----");
System.out.println(tree.search(7));
System.out.println("-----刪除結(jié)點7-----");
tree.delete(7);
tree.midSearch();
System.out.println("-----刪除結(jié)點4-----");
tree.delete(4);
tree.midSearch();
}
}