BST construction
refer to : https://www.algoexpert.io/questions/BST%20Construction
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