一.概念
二叉搜尋樹又稱二叉排序樹，具有以下性質：
- 若它的左子樹不為空，則左子樹上所有節點的值都小于根節點的值
- 若它的右子樹不為空，則右子樹上所有節點的值都大于根節點的值
- 它的左右子樹也分别為二叉搜尋樹
注意：二叉搜尋樹中序周遊的結果是有序的
二、基本操作
1.查找元素
思路：二叉搜尋樹的左子樹永遠是比根節點小的，而它的右子樹則都是比根節點大的值。目前節點比要找的大就往左走，目前元素比要找的小就往右走
public Node search(int key) {
if(root == null) {
return null;
}
Node cur = root;
while (cur != null) {
if(cur.val == key) {
return cur;
}else if(cur.val > key) {
cur = cur.left;
}else{
cur = cur.right;
}
}
return null;
}
2.插入元素
如果是空樹直接把元素插入root位置就好了
思路：因為是二叉搜尋樹就不能插入重複的元素了，且每次插入都是插入到葉子節點的位置。定義一個 cur 從root開始，插入的元素比目前位置元素小就往左走，比目前位置元素大就往右走，直到為空，是以就需要再定義一個變量parent 記住 cur 的前面的位置。
最後再判斷插入到parent 的左子樹還是右子樹位置
代碼實作：
public boolean insert(int key) {
Node node = new Node(key);
if(root == null) {
this.root = node;
return true;
}
Node parent = null;
Node cur = root;
while (cur != null) {
if(cur.val == key) {
//有相同的元素直接return
return false;
}else if(cur.val > key) {
parent = cur;
cur = cur.left;
}else{
parent = cur;
cur = cur.right;
}
}
if (parent.val > key) {
parent.left = node;
}else{
parent.right = node;
}
return true;
}
3.删除元素
删除元素是一個比較難的點，要考慮到很多種情況
- cur.left == null
- cur 是 root，則 root = cur.right
- cur 不是 root，cur 是 parent.left，則 parent.left = cur.right
- cur 不是 root，cur 是 parent.right，則 parent.right = cur.right
- cur.right == null
- cur 是 root，則 root = cur.left
- cur 不是 root，cur 是 parent.left，則 parent.left = cur.left
- cur 不是 root，cur 是 parent.right，則 parent.right = cur.left
-
cur.left != null && cur.right != null
采用替罪羊的方式删除
- 找到要删除節點，右樹最左邊的節點或者找到左樹最右邊的節點，替換這個兩個節點的val值。
- 這樣才能保證，删除後左樹一定比根節點小，右樹一定比根節點大
二叉搜尋樹(二叉排序樹)一.概念二、基本操作
public boolean remove(int key) {
if(this.root == null) {
return false;
}
Node parent = null;
Node cur = this.root;
while (cur != null) {
if(cur.val == key) {
removeKey(parent,cur);
return true;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else{
parent = cur;
cur = cur.left;
}
}
return false;
}
public void removeKey(Node parent,Node cur) {
if(cur.left == null) {
if(cur == this.root) {
this.root = this.root.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else{
parent.right = cur.right;
}
}else if(cur.right == null) {
if(this.root == cur) {
this.root = this.root.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else{
parent.right = cur.left;
}
}else{//左右都不為空的情況
Node targetParent = cur;
Node target = cur.right;
while (target.left != null) {
targetParent = target;
target = target.left;
}
cur.val = target.val;
if(targetParent.left == target) {
targetParent.left = target.right;
}else{
targetParent.right = target.right;
}
}
}
4.性能分析
插入和删除操作都必須先查找，查找效率代表了二叉搜尋樹中各個操作的性能
對有n個結點的二叉搜尋樹，若每個元素查找的機率相等，則二叉搜尋樹平均查找長度是結點在二叉搜尋樹的深度的函數，即結點越深，則比較次數越多。
但對于同一個關鍵碼集合，如果各關鍵碼插入的次序不同，可能得到不同結構的二叉搜尋樹：
最好情況：二叉搜尋樹為完全二叉樹，其平均比較次數為 O(log 2 _2 2n)
最壞情況：二叉搜尋樹退化為單支樹，其平均比較次數為：O
所有代碼：
public class BinarySearchTree {
public static class Node {
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
}
}
public Node root = null;
/**
* 查找某個節點
* @param key
*/
public Node search(int key) {
if(root == null) {
return null;
}
Node cur = root;
while (cur != null) {
if(cur.val == key) {
return cur;
}else if(cur.val > key) {
cur = cur.left;
}else{
cur = cur.right;
}
}
return null;
}
/**
* 插入元素
* @param key
* @return
*/
public boolean insert(int key) {
Node node = new Node(key);
if(root == null) {
this.root = node;
return true;
}
Node parent = null;
Node cur = root;
while (cur != null) {
if(cur.val == key) {
//有相同的元素直接return
return false;
}else if(cur.val > key) {
parent = cur;
cur = cur.left;
}else{
parent = cur;
cur = cur.right;
}
}
if (parent.val > key) {
parent.left = node;
}else{
parent.right = node;
}
return true;
}
/**
* 删除元素
* @param key
*/
public boolean remove(int key) {
if(this.root == null) {
return false;
}
Node parent = null;
Node cur = this.root;
while (cur != null) {
if(cur.val == key) {
removeKey(parent,cur);
return true;
}else if(cur.val < key) {
parent = cur;
cur = cur.right;
}else{
parent = cur;
cur = cur.left;
}
}
return false;
}
public void removeKey(Node parent,Node cur) {
if(cur.left == null) {
if(cur == this.root) {
this.root = this.root.right;
}else if(cur == parent.left) {
parent.left = cur.right;
}else{
parent.right = cur.right;
}
}else if(cur.right == null) {
if(this.root == cur) {
this.root = this.root.left;
}else if(cur == parent.left) {
parent.left = cur.left;
}else{
parent.right = cur.left;
}
}else{
Node targetParent = cur;
Node target = cur.right;
while (target.left != null) {
targetParent = target;
target = target.left;
}
cur.val = target.val;
if(targetParent.left == target) {
targetParent.left = target.right;
}else{
targetParent.right = target.right;
}
}
}
}