概念
二叉查找樹，也叫二叉搜索樹。樹中任意一個節(jié)點，該節(jié)點的左子樹中每個節(jié)點的值，都小于該節(jié)點的值；右子樹中每個節(jié)點的值，都大于該節(jié)點的值。
查找
從根節(jié)點開始查找，若查找的數(shù)據(jù)等于根節(jié)點的值，則返回；若查找的數(shù)據(jù)小于根節(jié)點的值，則在左子樹遞歸查找；若查找的數(shù)據(jù)大于根節(jié)點的值，則在右子樹遞歸查找。
插入
插入的數(shù)據(jù)一般會放置到葉子節(jié)點上，因此也是從根節(jié)點開始遍歷。
如果插入的數(shù)據(jù)比節(jié)點的數(shù)據(jù)大，且節(jié)點的右子樹為空，那么直接將插入數(shù)據(jù)作為右子樹節(jié)點；如果不為空，則循環(huán)遍歷右子樹，查找插入位置。
同理，如果插入的數(shù)據(jù)比節(jié)點數(shù)據(jù)小，且節(jié)點的左子樹為空，那么將插入數(shù)據(jù)作為左子樹節(jié)點；如果不為空，則循環(huán)遍歷左子樹，查找插入位置。
刪除
刪除二叉查找樹的操作分為三種情況：
一、刪除的節(jié)點沒有左右子樹，那么直接將父節(jié)點指向該刪除節(jié)點的指針，設(shè)置為null
二、刪除的節(jié)點有一個子節(jié)點，那么將父節(jié)點的指向刪除節(jié)點的指針，改為指向刪除節(jié)點的子節(jié)點
三、刪除的節(jié)點有兩個子節(jié)點，需要遍歷找到刪除節(jié)點的右子樹中最小的節(jié)點，將最小的節(jié)點替換到刪除節(jié)點上，最后將最小節(jié)點刪除
時間復(fù)雜度
時間復(fù)雜度和樹的高度成正比，即o(height)
一、最壞情況
若子節(jié)點都在某一側(cè)，就會退化成鏈表，時間復(fù)雜度為o(n)
二、最穩(wěn)定情況
對于n個節(jié)點的完全二叉樹來說，樹的高度介于這兩者之間：
n >= 1+2+4+8+...+2^(L-2)+1
n <= 1+2+4+8+...+2(L-2)+2(L-1)
L 的范圍是[log2(n+1), log2n +1]。完全二叉樹的層數(shù)小于等于 log(2底數(shù)) n +1，也就是說，完全二叉樹的高度小于等于 log(2底數(shù)) n。
顯然，極度不平衡的二叉查找樹，它的查找性能肯定不能滿足我們的需求。我們需要構(gòu)建一種不管怎么刪除、插入數(shù)據(jù)，在任何時候，都能保持任意節(jié)點左右子樹都比較平衡的二叉查找樹，因此衍生出一種特殊的二叉查找樹，平衡二叉查找樹。平衡二叉查找樹的高度接近 logn，所以插入、刪除、查找操作的時間復(fù)雜度也比較穩(wěn)定，是 O(logn)。
實戰(zhàn)題
leetcode 104題，如何求一顆二叉樹的高度
public int maxDepth(TreeNode root) {
if (root == null) return 0;
if (root.left == null && root.right == null) return 1;
int leftDepth = maxDepth(root.left);
int rightDepth = maxDepth(root.right);
return leftDepth >= rightDepth ? leftDepth + 1 : rightDepth + 1;
}
leetcode 450題，二叉查找樹的刪除操作
public TreeNode deleteNode(TreeNode root, int key) {
TreeNode del = root;
TreeNode delParent = null;
// 查找刪除節(jié)點
while (del != null) {
if (del.val == key) break;
if (key > del.val) {
delParent = del;
del = del.right;
} else {
delParent = del;
del = del.left;
}
}
if (del == null) return root;
// 若刪除節(jié)點的存在兩個子節(jié)點，找到右子樹的最小節(jié)點替換
if (del.left != null && del.right != null) {
TreeNode minDel = del.right;
TreeNode minDelParent = del;
while (minDel.left != null) {
minDelParent = minDel;
minDel = minDel.left;
}
del.val = minDel.val;
del = minDel;
delParent = minDelParent;
}
// 若刪除節(jié)點只存在一個子節(jié)點,或刪除節(jié)點沒有子節(jié)點
TreeNode child;
if (del.left != null) child = del.left;
else if (del.right != null) child = del.right;
else child = null;
// 刪除節(jié)點
if (delParent == null) return child;
else if (delParent.left == del) delParent.left = child;
else delParent.right = child;
return root;
}
