概念
二叉查找樹，也叫二叉搜索樹锯仪。樹中任意一個(gè)節(jié)點(diǎn)泵督，該節(jié)點(diǎn)的左子樹中每個(gè)節(jié)點(diǎn)的值，都小于該節(jié)點(diǎn)的值庶喜；右子樹中每個(gè)節(jié)點(diǎn)的值小腊，都大于該節(jié)點(diǎn)的值。
查找
從根節(jié)點(diǎn)開始查找久窟，若查找的數(shù)據(jù)等于根節(jié)點(diǎn)的值秩冈，則返回；若查找的數(shù)據(jù)小于根節(jié)點(diǎn)的值瘸羡，則在左子樹遞歸查找漩仙；若查找的數(shù)據(jù)大于根節(jié)點(diǎn)的值，則在右子樹遞歸查找犹赖。
插入
插入的數(shù)據(jù)一般會(huì)放置到葉子節(jié)點(diǎn)上队他，因此也是從根節(jié)點(diǎn)開始遍歷。
如果插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大峻村，且節(jié)點(diǎn)的右子樹為空麸折，那么直接將插入數(shù)據(jù)作為右子樹節(jié)點(diǎn)；如果不為空粘昨，則循環(huán)遍歷右子樹垢啼，查找插入位置窜锯。
同理，如果插入的數(shù)據(jù)比節(jié)點(diǎn)數(shù)據(jù)小芭析，且節(jié)點(diǎn)的左子樹為空锚扎，那么將插入數(shù)據(jù)作為左子樹節(jié)點(diǎn)；如果不為空馁启，則循環(huán)遍歷左子樹驾孔，查找插入位置。
刪除
刪除二叉查找樹的操作分為三種情況：
一惯疙、刪除的節(jié)點(diǎn)沒有左右子樹翠勉，那么直接將父節(jié)點(diǎn)指向該刪除節(jié)點(diǎn)的指針，設(shè)置為null
二霉颠、刪除的節(jié)點(diǎn)有一個(gè)子節(jié)點(diǎn)对碌，那么將父節(jié)點(diǎn)的指向刪除節(jié)點(diǎn)的指針，改為指向刪除節(jié)點(diǎn)的子節(jié)點(diǎn)
三蒿偎、刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)朽们，需要遍歷找到刪除節(jié)點(diǎn)的右子樹中最小的節(jié)點(diǎn)，將最小的節(jié)點(diǎn)替換到刪除節(jié)點(diǎn)上酥郭，最后將最小節(jié)點(diǎn)刪除
時(shí)間復(fù)雜度
時(shí)間復(fù)雜度和樹的高度成正比华坦，即o(height)
一愿吹、最壞情況
若子節(jié)點(diǎn)都在某一側(cè)不从，就會(huì)退化成鏈表，時(shí)間復(fù)雜度為o(n)
二犁跪、最穩(wěn)定情況
對(duì)于n個(gè)節(jié)點(diǎn)的完全二叉樹來說椿息，樹的高度介于這兩者之間：
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ù)钻心，在任何時(shí)候，都能保持任意節(jié)點(diǎn)左右子樹都比較平衡的二叉查找樹铅协，因此衍生出一種特殊的二叉查找樹捷沸，平衡二叉查找樹。平衡二叉查找樹的高度接近 logn狐史，所以插入痒给、刪除说墨、查找操作的時(shí)間復(fù)雜度也比較穩(wěn)定，是 O(logn)苍柏。
實(shí)戰(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é)點(diǎn)
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é)點(diǎn)的存在兩個(gè)子節(jié)點(diǎn)试吁，找到右子樹的最小節(jié)點(diǎn)替換
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é)點(diǎn)只存在一個(gè)子節(jié)點(diǎn),或刪除節(jié)點(diǎn)沒有子節(jié)點(diǎn)
TreeNode child;
if (del.left != null) child = del.left;
else if (del.right != null) child = del.right;
else child = null;
// 刪除節(jié)點(diǎn)
if (delParent == null) return child;
else if (delParent.left == del) delParent.left = child;
else delParent.right = child;
return root;
}
