二叉搜索樹：中序遍歷序列是有序的。

二叉查找樹，也稱有序二叉樹，是指一棵空樹或者具有以下性質的二叉樹：

• 左子節點的值比父節點小
• 右子節點的值比父節點大
• 任意節點的左右字樹也分別為二叉查找樹
• 沒有鍵值相等的點
• ?

在理想情況下，二叉查找樹增刪改查的時間復雜度為O(logN)；

二叉搜索樹的查找

使用遞歸！如果key小于當前節點，向當前節點的左子樹往下進行遞歸查找！如果key大于當前節點，向當前節點的右子樹往下進行遞歸查找！臨界條件是，當遞歸到節點為null都沒有找到時則返回。

二叉搜索樹的插入

插入時首先看當前key存不存在，存在的話返回，不存在的話插入！

將一個數組轉換成二叉搜索樹的結構！

首先數組第一個節點作為根節點！后面的節點小于根節點則向作為根節點的左孩子，反之作為右孩子。

二叉樹的刪除

難點在于：查找到要刪除的key之后，刪除！但是刪除之后如何依舊保持二叉搜索樹的特性！？

如果要刪除的節點只有左子樹或者右子樹的話，那很容易，直接將刪除節點的字樹填補到刪除節點！結果依然是BST！

如果要刪除的節點既有左子樹又有右子樹，怎么辦？

思路是：在左右子樹中找到能夠代替刪除節點的節點，填補到刪除位之后，依然保持BST特性！！！

其實也就是找到刪除節點在BST中序遍歷的直接前驅節點或者直接后繼節點！！！用此兩個節點中的一個來替換刪除節點！

因此：分為3種情況！

1）刪除的節點是葉子節點

2）刪除的節點只有左子樹或者右子樹

3）刪除的節點既有左子樹又有右子樹

//偽代碼 Status Delete(TreeNode root){TreeNode q = new TreeNode ();TreeNode s = new TreeNode ();//只有左子樹if(root.right == null){q = root;root = root.left;q.clear();}//只有右子樹else if(root.left == null){q = root;root = root.right;q.clear();} //既有左子樹又有右子樹else{q = p;s = p.left;while(s.right!=null){q = s;s = s.right;}p.val = s.val;//走到這里，s已經沒有右子樹了if(q!=p) q.right = s.left;//s左子節點即為葉子節點else q.left = s.left;s.clear();}return true; }

二叉樹的查找復雜度

但是若是二叉樹極度不平衡，形成了一個線性鏈后（左斜樹或者右斜樹），就會產生最壞運行情況O(N)。

基于BST存在的問題，平衡二叉樹產生了，典型的有AVL樹和紅黑樹，因為AVL是嚴格的平衡二叉樹，但是插入和刪除的性能較差，所以在實際生產環境中不如紅黑樹應用廣泛。

---

平衡二叉樹 AVL

維持BST的logn復雜度

定義：?

平衡二叉樹定義(AVL)：它或者是一顆空樹，或者具有以下性質的二叉樹：

前提，平衡二叉樹是一個二叉搜索樹

它的左子樹和右子樹的深度之差(平衡因子)的絕對值不超過1，且它的左子樹和右子樹都是一顆平衡二叉樹。

平衡因子(bf)：結點的左子樹的深度減去右子樹的深度，那么顯然-1<=bf<=1

平衡二叉樹的實現原理

在構建二叉搜索樹的過程中，每當我們插入一個新的節點的時候，先檢查插入節點是否破壞了樹的平衡性！如果破壞了，找出最小不平衡樹，在保證二叉搜索樹的的前提下，調整最小不平衡字樹種各節點的連接關系，進行相應的旋轉，使之成為新的平衡樹！

?

BF 平衡因子

當最小不平衡樹的根節點和其子節點的BF符號相同時：BF為負，左旋，BF為正，右旋。一次旋轉！

當最小不平衡樹的根節點和其子節點的BF符號不同時：先將他們的BF符號統一，再遵循? ?BF為負，左旋，BF為正，右旋。也即是進行兩次旋轉！

?

AVL節點結構

?

?

總結

以上是生活随笔為你收集整理的二叉搜索树（BST）？平衡二叉树（AVL）？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。