A?Binary Search Tree?is a special form of a binary tree. The value in each node must be?greater than?(or equal to) any values in its?left subtree?but?less than?(or equal to) any values in its?right subtree.
二叉查找樹的基本操作
The strength of a BST is that you can perform all search, insertion and deletion operations in?O(h)?time complexity even in the worst case.
查找一個節(jié)點
According to the property of BST, for each node:
1. return the node if the target value is?equal to?the value of the node;
2. continue searching in the?left?subtree if the target value is?less than?the value of the node;
3. continue searching in the?right?subtree if the target value is?larger than?the value of the node.
LeetCode?700.?Search in a Binary Search Tree
插入一個新節(jié)點
Similar to our search strategy, for each node, we will:
1. search the left or right subtrees according to the relation of the value of the node and the value of our target node;
2. repeat STEP 1 until reaching an external node;
3. add the new node as its left or right child depending on the relation of the value of the node and the value of our target node.
In this way, we add a new node and maintain the property of BST.
LeetCode?701.?Insert into a Binary Search Tree
刪除一個指定節(jié)點
1. If the target node has?no child, we can simply remove the node.
2. If the target node has?one child, we can use its child to replace itself.
3. If the target node has?two children, replace the node with its in-order successor or predecessor node and delete that node.
LeetCode?450.?Delete Node in a BST
兩點注意：
1. 刪除節(jié)點的方式很多清寇；實際中朵逝，如果節(jié)點的值是個很復(fù)雜的對象盈魁，這種通過交換被刪除節(jié)點和其后繼的值的方式钦幔，在實際中可能代價會比較大，不如直接交換引用（如以下實現(xiàn)）乐纸。
2. 如果被刪除節(jié)點的左右子樹均為空衬廷，那么可以將其左子樹作為其后繼節(jié)點的左子樹。不過這種方式有個缺點是汽绢，可能會加大樹的高度吗跋，從而使樹本身更加不平衡。以下實現(xiàn)中庶喜，通過改變左右子樹的引用小腊，返回其后繼節(jié)點作為新的根救鲤。
其他相關(guān)算法
非遞歸中序遍歷二叉樹模板可以有效地解決一些問題久窟。
LeetCode 94.?Binary Tree Inorder Traversal
LeetCode?230.?Kth Smallest Element in a BST
LeetCode?98.?Validate Binary Search Tree
LeetCode?173.?Binary Search Tree Iterator
引用：
Learn one iterative inorder traversal, apply it to multiple tree questions
