BST construction
1. 什么是二叉搜索树?
二叉搜索树是二叉树的一种特殊形式，而二叉树的特性在于每个节点包含最多两个子节点。
二叉搜索树的特性：每个节点的值都大于或等于它的左子树的值，小于或等于它的右子树的值，左子树和右子树分别也应该是BST。
Let x be a node in a bst, if y is a node in the left subtree of x, then y.key <= x.key. If y is a node in the right subtree of x, then y.key >= x.key.
--From 《Introduction to Algorithms. Third Edition》
2. Insertion && Search && Deletion (iterative method)
插入： 从根部开始遍历，比较当前节点的值和待插入的值，充分利用BST的特性，逐步eliminate half subtree（剪枝）直到找到没有子节点的适当位置（check if currNode.left/currNode.right == null or not），if it is, 直接插入该值, if not, continue eliminating half subtree。
Two big cases considered:
currNode.value > value &&
currNode.value <= value
查找： 从根部开始查找，比较当前节点的值和目标值，充分利用BST的特性，逐步eliminate half subtree（剪枝），找到之后(currNode.value == value), return true.
Three big cases considered:
currNode.value > value &&
currNode.value < value &&
currNode.value == value
删除： 主要分为两大步： step 1. 查找待删除的元素。 step 2.删除该元素
删除的时候有很多情况：
- currNode has two children
1. reassign the smallest value of the right subtree to currNode
currNode.value = currNode.right.getMinValue(); 2. remove the smallest value of the right subtree (currNode.value == leftmost value of the right subtree))
- currNode is at the root node and only has one child，
5. only has left child , 假如要删除5， currNode = 5,
/
3 3
\ / \
4. 2 4
/
2
5 only has right child. 假如要删除5， currNode = 5,
\
8. 8
/ / \
6. 6 7
\
7
一步步更新各个节点（记住）
if(currNode.left != null){
77 currNode.value = currNode.left.value; //把left.value挪到currNode
78 currNode.right = currNode.left.right;//大的值挪到右子树
79 currNode.left = currNode.left.left;//小的挪到左子树
80 }else if(currNode.right != null){
81 currNode.value = currNode.right.value;
82 currNode.left = currNode.right.left; //right.left must be less than right.value
83 currNode.right = currNode.right.right; //right.right must be larger than right.value
84 }else{
85 //currNode = null;
86 //this is a single-node tree; need to discuss with the interviewer
87 }
- currNode has one children, but the parentNode is not None，套用例子理解
5 假如要删除3，3 is currNode, 5 is the parentNode，4被挪到5的左子树，而根据bst的特性，它一定小于5
/
3
\
4
5 假如要删除7，7 is currNode, 5 is the parentNode，6会被挪到右子树，它一定大于5
\
7
/
6
充分利用parentNode
88 if(parentNode.left == currNode){ //parentNode != null
89 parentNode.left = （currNode.left != null ? currNode.left: currNode.right）;
90 }if(parentNode.right == currNode){
91 parentNode.right = （currNode.left != null ? currNode.left: currNode.right）;
92 }
In these cases, we allow the duplicate values, if any duplicates, let the value being the right child.
On average: O(logn) time complexity | O(1) space complexity
Worst case: O(n) time complexity | O(1) space complexity
1 import java.util.*;
2
3 class Program {
4 static class BST {
5 public int value;
6 public BST left;
7 public BST right;
8
9 public BST(int value) {
10 this.value = value;
11 }
12
13 public BST insert(int value) {
14 BST currNode = this;
15 while(true){
16 if(currNode.value > value){
17 if(currNode.left == null){
18 BST newNode = new BST(value);
19 currNode.left = newNode;
20 break; // successfully inserted
21 }else{
22 currNode = currNode.left;
23 }
24 }else{ //currNode.right <= value !!!notes
25 if(currNode.right == null){
26 BST newNode = new BST(value);
27 currNode.right = newNode;
28 break; //successfully inserted
29 }else{
30 currNode = currNode.right;
31 }
32 }
33 }
34 return this;
35 }
36
37 public boolean contains(int value) {
38 BST currNode = this;
39 while(currNode != null){
40 if(currNode.value > value){
41 currNode = currNode.left;
42 }else if(currNode.value < value){
43 currNode = currNode.right;
44 }else{ //currNode.value == value
45 return true;
46 }
47 }
48
49 return false;
50 }
51
52 public BST remove(int value) {
53 remove(value,null);
54 return this;
55 }
56
57 public void remove(int value, BST parentNode){
58 BST currNode = this;
59 //step 1. find the value
60 while(currNode != null){
61 if(currNode.value > value){
62 parentNode = currNode; //reassign the parentNode firstly.
63 currNode = currNode.left;
64 }else if(currNode.value < value){
65 parentNode = currNode;
66 currNode = currNode.right;
67 }else{ //we find the value, the next step is to remove this value
68 if(currNode.left != null && currNode.right != null){
69 //currNode has two children
70 //1. reassign the smallest value of the right subtree to currNode
71 currNode.value = currNode.right.getMinValue();
72 //2. remove the smallest value of the right subtree
73 //(currNode.value == leftmost value of the right subtree))
74 currNode.right.remove(currNode.value, currNode);
75 }else if(parentNode == null){
76 if(currNode.left != null){
77 currNode.value = currNode.left.value;
78 currNode.right = currNode.left.right;
79 currNode.left = currNode.left.left;
80 }else if(currNode.right != null){
81 currNode.value = currNode.right.value;
82 currNode.left = currNode.right.left;
83 currNode.right = currNode.right.right;
84 }else{
85 //currNode = null;
86 //this is a single-node tree; need to discuss with the interviewer
87 }
88 }else if(parentNode.left == currNode){ //parentNode != null
89 parentNode.left = currNode.left != null ? currNode.left: currNode.right;
90 }else if(parentNode.right == currNode){
91 parentNode.right = currNode.left != null ? currNode.left: currNode.right;
92 }
93 break;
94 }
95 }
96 }
97
98 public int getMinValue(){
99 if (left == null){
100 return value;
101 }else{
102 return left.getMinValue();
103 }
104 }
105 }
106 }
1 class BST: 2 def __init__(self, value): 3 self.value = value 4 self.left = None 5 self.right = None 6 7 def insert(self, value): 8 currNode = self 9 while True: #True, uppercase 10 if currNode.value > value: 11 if currNode.left is None: 12 currNode.left = BST(value) 13 break # do not forget break!!! 14 else: 15 currNode = currNode.left 16 else: 17 if currNode.right is None: 18 currNode.right = BST(value) 19 break # do not forget break!!! 20 else: 21 currNode = currNode.right 22 return self 23 24 def contains(self, value): 25 currNode = self 26 while currNode is not None: # is not while True in this case!!! 27 if currNode.value > value: 28 currNode = currNode.left 29 elif currNode.value < value: 30 currNode = currNode.right 31 else: 32 return True 33 return False # never found the value 34 35 36 def remove(self, value, parentNode = None): 37 # step 1. find the value you want to remove 38 currNode = self 39 while currNode is not None: 40 if currNode.value > value: 41 parentNode = currNode # trace the parentNode 42 currNode = currNode.left 43 elif currNode.value < value: 44 parentNode = currNode 45 currNode = currNode.right 46 # step 2. remove this value 47 48 else: # find the value 49 # case 1, the currNode has two children 50 if currNode.left is not None and currNode.right is not None: 51 #resign the currNode value to the smallest value 52 currNode.value = currNode.right.getMinValue() 53 # remove the smallest value 54 currNode.right.remove(currNode.value, currNode) 55 elif parentNode is None: # at the root node and only has one child 56 if currNode.left is not None: 57 currNode.value = currNode.left.value 58 currNode.right = currNode.left.right 59 currNode.left = currNode.left.left #ressign the currNode.left at last 60 elif currNode.right is not None: 61 currNode.value = currNode.right.value 62 currNode.left = currNode.right.left 63 currNode.right = currNode.right.right#ressign the currNode.right at last 64 else: 65 # this is a single-node; do nothing 66 # discuss with the interviewer 67 # currNode.value = None 68 pass 69 # case 2, the node has one children, but the parentNode is not None 70 elif parentNode.left == currNode: # the currNode is the left child 71 parentNode.left = currNode.left if currNode.left is not None else currNode.right 72 elif parentNode.right == currNode: 73 parentNode.right = currNode.left if currNode.left is not None else currNode.right 74 # 5 75 #/ 76 #3 77 #\ 78 #4 79 break 80 81 return self 82 83 def getMinValue(self): 84 currNode = self 85 while currNode.left is not None: 86 currNode = currNode.left 87 return currNode.value # currNode.left is None