# 二元搜尋樹概念

[toc]

> 二元搜尋樹會有規則，所以在做搜尋上會較簡單， 但是二元樹，很雜亂，所以只能透過地回和一一比對去做

# 二元樹和二元搜尋樹概念

- Not every level must be completely filled 就是不需要必定為completed tree
- （最主要跟一般二元樹的差別）**任一個節點的左子樹都比父節點小，右子樹都比父節點大，且每一個節點的值都不重複**。
- 所以當我們要查找資料的時候，就可以從根節點開始，比根節點小的就從左子樹開始找，比較大的就從右子樹開始找。相對於其他資料結構而言，尋找、插入的時間複雜度較低，為Ｏ(logN)。
- 所以整個Tree最小的那個node 因該會在最左最下的那個node ，最大的則是最右最下的那個node
- In a Binary Search Tree (BST), all keys in left subtree of a key must be smaller and all keys in right subtree must be greater. So a Binary Search Tree by definition has distinct keys and duplicates in binary search tree are not allowed. 記得所有的value不可重複****

# 二元搜尋樹 big o

搜尋 : 平均時間複雜度 log(n)，因為只要往其中一邊走。
新增 : 平均時間複雜度 log(n)，因為它要找到適當的插入位置
刪除 : 平均時間複雜度 log(n)，因為它要找到適當的移除位置

## 平衡二元搜尋樹 ( Balanced BST )
BST 平均來看基本操作都有指數級的時間複雜度，但為什麼還是沒選他呢 ?

主要的原因在於，它最壞變成 O(n) 的時間複雜度操作，如下圖 5 所示，它的確也是一個 BST，這樣如果我們要搜尋某個值，仍然是一個一個慢慢找。


圖 5 : 有問題的 BST

因為後來就誕生一種『 平衡二元搜尋樹 』，如下圖 6 所示，事實和上面二元樹相同，只是差在每當插入節點時，會進行平衡。

它的特點如下 :

葉節點的高度差的絕對值不能超過 1。
左右子樹都為平衡二元搜尋樹。
它的最好、最壞、平均的新增、刪除、搜尋的時間複雜度都是 O (logn)。
AVL 樹、紅黑樹都是屬於平衡二元搜尋樹，它們都會自動的進行平衡操作。

圖 6 : 平衡二元樹

平衡二元搜尋樹，正常來說，已經是在搜尋中最有效率的資料結構了，但是為什麼它是沒選它呢 ?
因為它是以『 記憶體 』來說，操作最有效率，但是以『 硬碟 』來說則否。

在資料庫的世界，通常資料量都有點兒大，不太可能全部都塞在記憶體中操作，通常會放在硬碟中。

那為什麼平衡二元搜尋樹在硬碟中操作沒有什麼效率呢 ?
因為 I/O 的問題

然後你想想如果一個很深的平衡二元搜尋樹，那如果要找的值是在最小面，以下圖 7 為例，那它就至少要進行 100 次 i/o 操作。


圖 7 : 平衡二元樹在節點多時的問題
B 樹
根據上述 i/o 的原因，因此又誕生出叫『 B 樹 』的東東，它想解決的東西為 :+1 :+1:
:8ball:

當樹太大就要多次io處理：
是的，當樹的大小超過了系統的內存容量時，可能需要進行多次IO操作才能處理整個樹。這是因為內存容量有限，無法一次性將整個樹加載到內存中進行操作。

外部存儲器算法需要考慮到IO操作的效率和數據讀取的順序，以最大限度地減少IO次數和數據讀取的開銷。常見的技術包括使用緩存（cache）來減少IO操作、按照順序讀取數據以提高讀取效率、以及使用索引或搜索樹結構來加速節點查找等。

-[b tree](/g9s0omRrSmmRQbcRKJQDVw)

# 二元搜尋樹搜尋、新增、改值、刪除四種操作

## **新增節點**

假設我們今天要把值為 15 和 40 的節點新增進去

先做 15 的節點：
1. 與 root 節點 ( 20 ) 比較，15 < 20，左子樹不為空，往左子樹走
2. 與節點 ( 10 ) 比較，10 < 15，右子樹為空，就把 15 填進去

相信聰明的你已經知道怎麼新增節點了，試試看把 40 新增進去吧。

沒錯就是這樣，按照上面的邏輯 40 就應該放在 30 的右邊（右子樹）。


## **搜尋結點**

假設我們要搜尋 15 這個節點，**其實跟新增的步驟差不多**，先逐一比大小，差在要確認經過的節點的值是不是 15 即可。

1. 與 root 節點 ( 20 ) 比較，15 < 20，往左子樹走
2. 與節點 ( 10 ) 比較，10 < 15，往右子樹走
3. 與節點 ( 15 ) 比較，15 == 15，找到了！

## **修改節點的值**

我上網查發現沒有什麼人講到如果要改值的話怎麼操作最有效率，但最簡單的方法應該是就把該舊值的節點刪除，然後插入更新值的節點。

## 刪除節點的值(有幾種情況)

1. 第一種情況：在最leaf 的node 直接delete 就好，因為你不需要重新排序他。

2. 第二種情況：如果是在父節點上，然後這個父節點只有一個子樹(左子樹or 右子樹)就把樹刪掉，然後讓子樹串上去，指標指上去就好
刪掉父節點，補上子節點。

3. 第三種情況： 如果你要刪除的節點有很多子樹
但如果你是在父節點上，且你有兩層以上的子樹，那你要找的接替者succesor

如下圖，我們要刪除70， 並且補上70的位置，然後再讓85補上

會找到80的位置，因為比你要保持binary search tree的規律，所以要剛好藉在50<x<90之間 如果我們找90的右子樹，那麼他必定比9０大，就不合理，那如果我們找90的左子樹，可以知道這個數字必定比90小，但右一定比50大(所以才會第一關跑來90這個子樹，而不是跑去50 )
至於要怎麼找出80這個位置：
如下圖，總而言之就是，我們要找到目前要刪除的點的子數中最大的那個樹（整個binary search tree 依照priority 排出順序後，你要刪除的node的前一個順位的那一個node就是你的補貼者）因為比你這個要刪出node更大的，可能會到刪除node的父子樹的右子樹去，
如果你要刪除的是左子樹→找最大的
如果你要刪除的是右子樹→找最小的

- [ＢＴＳ_ＣＲＵＤ完整程式碼](/stXJ17WyTX2kKszE7mHDag)

# 二元搜尋樹插入概念(補充)

## 插入概念
和搜尋很像，從根節點開始比大小，比較小的往左子樹走，比較大的往右子樹走，一樣的則返回，直到插入為止(要邊排邊插入。

如果單純只是二元樹的插入話，就是插入在complete tree 上最後一個leaf 而已)。因為二元樹的建立沒有大小之分。

# 二元搜尋樹部分code(插入新的node )

思路：

- 把每個子樹當作一個part ，每個子樹有父子樹以及左右子樹。每次地迴，就是再去下一個子樹part 去看。
- 因為BST的規則，父子樹要大於左子樹，所以我們必須要傳入兩個參數，要加入的點，以及父子樹，因為要做比較
- 然後比較父子樹和要加入的點的大小，如果小就往左邊地回，然後把左子樹看成新的子樹part 如第一步驟，反之如果比較大就往右邊走，然後一樣。

## 二元搜尋樹部分code(插入新的node )程式碼

import QueueLinkedList as queue

class BSTNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None

def insertNode(rootNode, nodeValue): # 必須傳入父節點，和子節點
#---------------先判斷有沒有樹
if rootNode.data == None: # 判斷是否有值
rootNode.data = nodeValue
#-----------------
elif nodeValue < rootNode.data: # 比對目前的這個節點是否小於你要插入的節點(放到左子樹)
if rootNode.leftChild is None:
rootNode.leftChild = BSTNode(nodeValue) # 如果左子樹為空，就建立左子樹
else:
insertNode(rootNode.leftChild, nodeValue) #遞迴：如果左子樹不為空，就繼續尋找下去
elif nodeValue >rootNode.data:
if rootNode.rightChild is None: # 同上的原理 只是變成右邊
rootNode.rightChild = BSTNode(nodeValue)
else:
insertNode(rootNode.rightChild, nodeValue)
else:
return "can not allowed duplicated value "
return "The node has been successfully inserted

## BST 全部程式碼

# Created by Elshad Karimov
# Copyright © 2020 AppMillers. All rights reserved.

import QueueLinkedList as queue

class BSTNode:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None

def insertNode(rootNode, nodeValue): # 必須傳入父節點，和子節點
#---------------先判斷有沒有樹
if rootNode.data == None: # 判斷是否有值
rootNode.data = nodeValue
#-----------------
elif nodeValue <= rootNode.data: # 比對目前的這個節點是否小於你要插入的節點(放到左子樹)
if rootNode.leftChild is None:
rootNode.leftChild = BSTNode(nodeValue) # 如果左子樹為空，就建立左子樹
else:
insertNode(rootNode.leftChild, nodeValue) #遞迴：如果左子樹不為空，就繼續尋找下去
else:
if rootNode.rightChild is None: # 同上的原理 只是變成右邊
rootNode.rightChild = BSTNode(nodeValue)
else:
insertNode(rootNode.rightChild, nodeValue)
return "The node has been successfully inserted"

def preOrderTraversal(rootNode): # travel 方法，一樣和之前的一般binary tree 一樣
if not rootNode:
return
print(rootNode.data)
preOrderTraversal(rootNode.leftChild)
preOrderTraversal(rootNode.rightChild)

def inOrderTraversal(rootNode):
if not rootNode:
return
inOrderTraversal(rootNode.leftChild)
print(rootNode.data)
inOrderTraversal(rootNode.rightChild)

def postOrderTraversal(rootNode):
if not rootNode:
return
postOrderTraversal(rootNode.leftChild)
postOrderTraversal(rootNode.rightChild)
print(rootNode.data)

## level order 的方法 跟binary tree 一模一樣
def levelOrderTraversal(rootNode):
if not rootNode:
return
else:
customQueue = queue.Queue()
customQueue.enqueue(rootNode)
while not(customQueue.isEmpty()):
root = customQueue.dequeue()
print(root.value.data)
if root.value.leftChild is not None:
customQueue.enqueue(root.value.leftChild)
if root.value.rightChild is not None:
customQueue.enqueue(root.value.rightChild)

def searchNode(rootNode, nodeValue):
if rootNode.data == nodeValue:
print("The value is found")
elif nodeValue < rootNode.data: # 跟上面的插入很像， 因為你在插入的動作，就需要去做排序比較 ，這個binary search tree的原則
if rootNode.leftChild.data == nodeValue:
print("The value is found")
else:
searchNode(rootNode.leftChild, nodeValue) # 做地迴
else:
if rootNode.rightChild.data == nodeValue:
print("The value is found")
else:
searchNode(rootNode.rightChild, nodeValue)

def minValueNode(bstNode): # binary search tree 最小值會發生在最左邊且最下面的那個leaf
current = bstNode
while (current.leftChild is not None):
current = current.leftChild
return current

def deleteNode(rootNode, nodeValue):
if rootNode is None:
return rootNode
if nodeValue < rootNode.data:
rootNode.leftChild = deleteNode(rootNode.leftChild, nodeValue)
elif nodeValue > rootNode.data:
rootNode.rightChild = deleteNode(rootNode.rightChild, nodeValue)
else:
if rootNode.leftChild is None:
temp = rootNode.rightChild
rootNode = None
return temp

if rootNode.rightChild is None:
temp = rootNode.leftChild
rootNode = None
return temp

temp = minValueNode(rootNode.rightChild) # 從右子樹去找最小的，固定的，假設我們把我要刪除的那個點，當作根節點來看的話
rootNode.data = temp.data #這個最小的直是我們要替換的對象，所以我們會return 他
rootNode.rightChild = deleteNode(rootNode.rightChild, temp.data)# 這個code是要刪掉我們找到的那個最小的直，所以再一次地迴
return rootNode

def deleteBST(rootNode):
rootNode.data = None
rootNode.leftChild = None
rootNode.rightChild = None
return "The BST has been successfully deleted"

newBST = BSTNode(None)
insertNode(newBST, 70)
insertNode(newBST,50)
insertNode(newBST,90)
insertNode(newBST, 30)
insertNode(newBST,60)
insertNode(newBST,80)
insertNode(newBST,100)
insertNode(newBST,20)
insertNode(newBST,40)
print(deleteBST(newBST))
levelOrderTraversal(newBST)