<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script> # Binary Search Tree(Ordered Binary Tree) - 二叉查找樹（有序二叉樹） -------- #### 二叉查找樹 二叉查找樹和二分查找算法的核心一樣，但使用樹形結構來實現。  二叉查找樹上節點$$ x $$的左孩子節點為$$ left_{x} $$，右孩子節點為$$ right_{x} $$，恒有$$ left_{x} \lt x \lt right_{x} $$。二叉查找樹中不允許兩個相等的節點（通過一些方法可以實現重復鍵值的二叉查找樹，但為了方便本文中不考慮這種情況）。 擁有$$ n $$個節點且安排良好的（金字塔型的）二叉查找樹從根節點向下可以在$$ O(log_2 n) $$的時間復雜度內查找到任意元素。二叉查找樹上任意節點$$ x $$的左子樹上所有節點都小于$$ x $$，右子樹上所有節點都大于$$ x $$。在二叉查找樹上查詢一個節點的過程和二分查找完全一樣，從根節點開始依次比較被查找的節點$$ x $$和當前節點$$ e $$，若$$ x = e $$則查找結束；若$$ x \lt e $$則繼續在左子樹中查找；若$$ x \gt e $$則繼續在右子樹中查找：  二叉樹的遍歷有： $$ (1) $$ 先序遍歷（$$ PreOrder $$），訪問順序總是$$ x \rightarrow left_{x} \rightarrow right_{x} $$； $$ (2) $$ 后序遍歷（$$ PostOrder $$），訪問順序總是$$ left_{x} \rightarrow right_{x} \rightarrow x $$； $$ (3) $$ 中序遍歷（$$ InOrder $$），訪問順序總是$$ left_{x} \rightarrow x \rightarrow right_{x} $$； $$ (4) $$ 層序遍歷（$$ LevelOrder $$），訪問順序類似BFS算法，一層一層的訪問所有節點）； 下圖中節點的訪問順序按照數字從小到大：   往二叉查找樹插入節點$$ x $$時，首先在樹上嘗試搜索$$ x $$，搜索失敗時會停下的節點$$ e $$就是合適插入的位置。若$$ x \lt e $$則將其作為$$ e $$的左孩子節點，若$$ x \gt e $$則將其作為$$ e $$的右孩子節點。為了方便我們不考慮重復插入$$ x $$的情況。  從二叉查找樹中刪除節點$$ x $$時需要保證二叉查找樹的屬性（$$ left_{x} \lt x \lt right_{x} $$），有三種情況： $$ (1) $$ 若$$ x $$為葉子節點，既沒有左孩子節點也沒有右孩子節點，直接刪除； $$ (2) $$ 若$$ x $$只有一個孩子節點$$ y $$，則像鏈表一樣將$$ x $$從其父節點和$$ y $$之間刪除； $$ (3) $$ 若$$ x $$同時有左右孩子節點，按照中序遍歷找出二叉樹中比$$ x $$大的下一個節點$$ next $$（中序遍歷下的后繼節點），用其值代替$$ x $$，實際刪除節點$$ next $$； 下圖演示了上述的三種刪除情況：    隨機的插入/刪除會讓二叉查找樹退化為鏈表，如圖所示是一個糟糕的二叉查找樹，雖然它滿足節點之間有序，但是查找的時間復雜度已經退化為了$$ O(n) $$。  -------- #### 源碼 [BinarySearchTree.h](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/BinarySearchTree.h) [BinarySearchTree.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/BinarySearchTree.cpp) #### 測試 [BinarySearchTreeTest.cpp](https://github.com/linrongbin16/Way-to-Algorithm/blob/master/src/DataStructure/BinarySearchTreeTest.cpp)