BST construction

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

 

 

 

 

上一篇:BST、AVL、红黑树,B-树、B+树


下一篇:653. Two Sum IV - Input is a BST