Snapchat video面经

不需要考虑balanced tree么？ 以及这道题目跟实现一个int类型BST的区别是什么。。

所以这道题是要实现一个BST，但是BST的node里存的是int类型的key-value pair？

1. public class MyHashtable {
   
2.        
   
3.         private Pair root;
   
4.         private int size;
   
5.        
   
6.         public MyHashtable() {
   
7.                 root = null;
   
8.                 size = 0;
   
9.         }
   
10.        
    
11.         public int get(int k) {
    
12.                 Pair node = search(root, k);
    
13.                 if (node == null) {
    
14.                         throw new NoSuchElementException();
    
15.                 }
    
16.                 return node.val;
    
17.         }
    
18.        
    
19.         private Pair search(Pair node, int k) {
    
20.                 if (node == null) {
    
21.                         return null;
    
22.                 }
    
23.                 if (node.key == k) {
    
24.                         return node;
    
25.                 }
    
26.                 if (node.key < k) {
    
27.                         return search(node.right, k);
    
28.                 }
    
29.                 return search(node.left, k);
    
30.         }
    
31.        
    
32.         public void put(int k, int v) {
    
33.                 if (root == null) {
    
34.                         root = new Pair(k, v);
    
35.                         return;
    
36.                 }
    
37.                 Pair node = search(root, k);
    
38.                 if (node != null) {
    
39.                         node.val = v;
    
40.                 } else {
    
41.                         node = new Pair(k, v);
    
42.                         insert(root, node);
    
43.                 }
    
44.         }
    
45.        
    
46.         private void insert(Pair node, Pair newNode) {
    
47.                 if (node.key < newNode.key) {
    
48.                         if (node.right == null) {
    
49.                                 node.right = newNode;
    
50.                         } else {
    
51.                                 insert(node.right, newNode);
    
52.                         }
    
53.                 } else {
    
54.                         if (node.left == null) {
    
55.                                 node.left = newNode;
    
56.                         } else {
    
57.                                 insert(node.left, newNode);
    
58.                         }
    
59.                 }
    
60.         }
    
61.        
    
62.         public boolean remove(int k) {
    
63.                 if (!containsKey(k)) {
    
64.                         return false;
    
65.                 }
    
66.                 root = remove(root, k);
    
67.                 return true;
    
68.         }
    
69.        
    
70.         private Pair remove(Pair node, int k) {
    
71.                 if (node == null) {
    
72.                         return null;
    
73.                 }
    
74.                 if (node.key < k) {
    
75.                         node.right = remove(node.right, k);
    
76.                 } else if (node.key > k) {
    
77.                         node.left = remove(node.left, k);
    
78.                 } else {
    
79.                         if (node.left == null) {
    
80.                                 return node.right;
    
81.                         }
    
82.                         if (node.right == null) {
    
83.                                 return node.right;
    
84.                         }
    
85.                         Pair temp = node;
    
86.                         node = min(temp.right);
    
87.                         node.right = deleteMin(temp.right);
    
88.                         node.left = temp.left;
    
89.                 }
    
90.                 return node;
    
91.         }
    
92.        
    
93.         private Pair min(Pair node) {
    
94.                 if (node.left == null) {
    
95.                         return node;
    
96.                 }
    
97.                 return min(node.left);
    
98.         }
    
99.        
    
100.         private Pair deleteMin(Pair node) {
     
101.                 if (node.left == null) {
     
102.                         return node.right;
     
103.                 }
     
104.                 node.left = deleteMin(node.left);
     
105.                 return node;
     
106.         }
     
107.        
     
108.         private boolean containsKey(int k) {
     
109.                 return containsKey(root, k);
     
110.         }
     
111.        
     
112.         private boolean containsKey(Pair node, int k) {
     
113.                 if (node == null) {
     
114.                         return false;
     
115.                 }
     
116.                 if (node.key == k) {
     
117.                         return true;
     
118.                 }
     
119.                 if (node.key < k) {
     
120.                         return containsKey(node.right, k);
     
121.                 } else {
     
122.                         return containsKey(node.left, k);
     
123.                 }
     
124.         }
     
125.        
     
126.         public int size() {
     
127.                 return size;
     
128.         }
     
129.        
     
130.         class Pair {
     
131.                 int key;
     
132.                 int val;
     
133.                 Pair left;
     
134.                 Pair right;
     
135.                 public Pair(int k, int v) {
     
136.                         key = k;
     
137.                         val = v;
     
138.                         left = null;
     
139.                         right = null;
     
140.                 }
     
141.         }
     
142.        
     
143.        
     
144.         public static void main(String[] args) {
     
145.                 MyHashtable table = new MyHashtable();
     
146.                 table.put(1, 6);
     
147.                 table.put(2, 7);
     
148.                 table.put(3, 8);
     
149.                
     
150.                 System.out.println(table.get(1));
     
151.                 System.out.println(table.get(2));
     
152.                 System.out.println(table.get(3));
     
153.                 table.put(4, 10);
     
154.                 System.out.println(table.get(4));
     
155.                 table.remove(4);
     
156. //                System.out.println(table.get(4));
     
157.                 System.out.println(table.get(1));
     
158.                 table.remove(1);
     
159. //                System.out.println(table.get(1));
     
160.         }
     
161. 
     
162. }
     

复制代码

个人理解应该是BST实现Dictionary接口的意思吧，除了Key其他作为卫星数据？
普通BST还行，RB和AVL是真写不出来，左旋右旋……