什么是搜索樹

搜索樹是一種樹形數據結構，用于高效地存儲和檢索數據。其核心特點是每個節點包含一個鍵（Key），并遵循特定的排序規則。常見的搜索樹有二叉搜索樹、自平衡二叉樹、多叉搜索樹等。AVL樹、紅黑樹、Splay樹都屬于自平衡二叉樹。

二叉搜索樹

什么是二叉搜索樹

1、是一棵二叉樹
2、左子樹所有節點值的大小 < 當前節點值的大小
3、右子樹所有節點值的大小 > 當前節點值的大小
4、子樹也滿足上述條件
下圖就是一棵二叉搜索樹：

根據二叉搜索樹的性質，當我們中序遍歷這棵樹的時候，發現它是按照順序進行排序的。（上面中序排序為：10、20、30、40、50、60、70、80）

二叉搜索樹的基本操作

查找

根據二叉搜索樹的性質，“左邊的值”都比節點的值小，“右邊的值”都比節點的值大。這樣我們查找的時候就可以直接排除了一邊子樹。

代碼展示：

public TreeNode search(int key) {if(root == null) {return null;}TreeNode cur = root;while (cur != null) {if(cur.value == key) {return cur;}else if(cur.value > key) {//說明key在左樹cur = cur.left;}else {//說明key在右樹cur = cur.right;}}return null;//當整棵樹都沒有找到key，返回null
}

代碼分析：

時間復雜度：最好情況下（根節點就是要找的）：O(1)；平均情況下：O(logN) —> 每次比較可以排除一半的節點，類似二分查找；最壞情況下（樹是一棵單邊樹，也看成鏈表）：O(N) -----> 需要遍歷每個節點。

為了解決二叉搜索樹存在的問題，就有了AVL樹、紅黑樹

插入

插入數據后，還是要滿足二叉搜索樹的性質的。插入操作一般都是在葉子節點位置進行的。這是為了保證插入后樹依然保持二叉搜索樹的性質，并且不需要對已有的其他節點結構進行調整。

代碼展示：

public boolean insert(int val) {TreeNode node = new TreeNode(val);//當二叉樹為空，直接插入if(root == null) {root = node;return true;}TreeNode cur = root;//用來找到遍歷二叉樹TreeNode prev = null;//用來找到cur父親節點while (cur != null) {if(cur.value == val) {return false;}else if(cur.value > val) {prev = cur;cur = cur.left;//根據性質，需要在左子樹進行插入，cur向左子樹移動。}else {prev = cur;cur = cur.right;//根據性質，需要在右子樹進行插入，cur向右子樹移動。}}//此時cur為null，prev指向cur父親節點//根據prev的值決定將新節點插入左子樹還是右子樹if(prev.value > val) {prev.left = node;}else {prev.right = node;}return true;
}

代碼分析：

時間復雜度：平均情況下：O(logN)；最壞情況下（樹是一棵單邊樹，也看成鏈表）：O(N)。

刪除

代碼展示：

public void remove(int val) {if(root == null) {return;}TreeNode cur = root;TreeNode parent = null;if(cur.val > val) {parent = cur;cur = cur.left;}else if(cur.val < val) {parent = cur;cur = cur.right;}else {parent = cur;removeNode(cur,parent);//通過上述代碼找到要刪除的節點，再通過removeNode(cur,parent)方法刪除節點}
}
//刪除節點的方法
private void removeNode(TreeNode cur, TreeNode parent) {//1、cur.left == null：要刪除的節點只有右節點if(cur.left == null) {if(cur == root) { //1.1、cur為root，則root = cur.rightroot = cur.right;//要刪除的為根節點，根節點往后移}else {if(cur == parent.right) {//1.2、cur不為root，cur為父親節點(parent)的右結點parent.right = cur.right;//讓parent的右節點指向cur的右節點，跳過cur}else {//1.3、cur不為root，cur為父親節點(parent)的左結點parent.left = cur.right;//讓parent的左節點指向cur的右節點，跳過cur}}}else if(cur.right == null) {//2、cur.right == nullif(cur == root) { //2.1、cur為root，則root = cur.leftroot = cur.left;//要刪除的為根節點，根節點往后移}else {if(cur == parent.right) {//2.2、cur不為root，cur為父親節點(parent)的右結點parent.right = cur.left;//讓parent的右節點指向cur的左節點，跳過cur}else {//2.3、cur不為root，cur為父親節點(parent)的左結點parent.left = cur.left;//讓parent的左節點指向cur的左節點，跳過cur}}}else {//3、cur.left != null && cur.right != null//這里的刪除相當于替換刪除。在以cur為root的樹中，在右樹找到最左邊的節點（或者在左樹找到最右邊的節點）TreeNode target = cur.right;TreeNode targetParent = cur;while (target.left != null) {//在右樹找到最左邊的節點targettargetParent = target;target = target.left;}cur.val = target.val;//target在targetParent的左右子樹位置不一樣，刪除方式不一樣if(target == targetParent.left) {targetParent.left = target.right;}else {targetParent.right = target.right;}}
}

代碼分析：