使用java实现二叉查找树的插入，修改和删除方法

目前使用的是根据key的hashcode来进行排序，并且没有考虑hash碰撞的问题

  1 package com.zhou.tree;
  2 
  3 import java.util.Comparator;
  4 import java.util.HashMap;
  5 import java.util.Map;
  6 
  7 /**
  8  * @Description:
  9  * @author: zhoum
 10  * @Date: 2019-05-16
 11  * @Time: 9:44
 12  */
 13 public class BinarySearchTree<K,V> {
 14 
 15     private Node root;
 16 
 17     private class Node{
 18 
 19         private K key;
 20 
 21         private V value;
 22 
 23         private Node left,right,parent;
 24 
 25         public Node(K k,V v,Node parent) {
 26             this.key = k;
 27             this.value = v;
 28             this.parent = parent;
 29         }
 30     }
 31 
 32     public BinarySearchTree() {}
 33 
 34     public void put(K k,V v){
 35         if( k == null){ return; }
 36         if(root == null){
 37             root = new Node(k,v,null);
 38             return;
 39         }
 40         insert(root,k,v);
 41 
 42     }
 43 
 44     private void insert(Node node,K k,V v){
 45         if(k.hashCode() == node.key.hashCode() && k.equals(node.key)){
 46             node.value = v;
 47         }else if(k.hashCode() > node.key.hashCode()){
 48             if(node.right == null){
 49                 Node n = new Node(k,v,node);
 50                 node.right = n;
 51             }else {
 52                 insert(node.right,k,v);
 53             }
 54         }else {
 55             if(node.left == null){
 56                 Node n = new Node(k,v,node);
 57                 node.left = n;
 58             }else {
 59                 insert(node.left,k,v);
 60             }
 61         }
 62     }
 63 
 64 
 65     public V get(K k){
 66         if(root == null || k == null){
 67             return null;
 68         }
 69         return get(root,k).value;
 70     }
 71 
 72     private Node get(Node node,K k){
 73         if(node == null){
 74             return null;
 75         }else if(node.key.hashCode() == k.hashCode() && node.key.equals(k)){
 76             return node;
 77         }else if(k.hashCode() > node.key.hashCode()){
 78             if(node.right == null){
 79                 return null;
 80             }
 81             return get(node.right,k);
 82         }else {
 83             if(node.left == null){
 84                 return null;
 85             }
 86             return get(node.left,k);
 87         }
 88 
 89     }
 90     public boolean delete(K k){
 91         Node node = get(root , k);
 92         if(node == null){
 93             return false;
 94         }
 95         //被删除节点右孩子为空
 96         if(node.right == null){
 97             //根节点
 98             if(node.parent == null){
 99                if(node.left == null){
100                    root = null;
101                    return true;
102                }
103                 root = node.left;
104                 root.parent = null;
105                 return true;
106             }
107             if(node.parent.left != null && node.key.equals(node.parent.left.key)){
108                 if(node.left == null){
109                     node.parent.left = null;
110                 }else {
111                     node.parent.left = node.left;
112                     node.left.parent = node.parent;
113                 }
114 
115             }else if(node.parent.right != null && node.key.equals(node.parent.right.key)){
116                 if(node.left == null){
117                     node.parent.right = null;
118                 }else {
119                     node.parent.right = node.left;
120                     node.left.parent = node.parent;
121                 }
122 
123             }
124             return true;
125 
126         }
127         //被删除节点左孩子为空
128         if(node.left == null){
129             //如果为根节点
130             if(node.parent == null){
131                 if(node.right == null){
132                     root = null;
133                     return true;
134                 }
135                 root = node.right;
136                 root.parent = null;
137                 return true;
138             }
139             if(node.parent.left.key.equals(node.key) ){
140                 if(node.right == null){
141                     node.parent.left = null;
142                 }else {
143                     node.parent.left = node.right;
144                     node.right.parent = node.parent;
145                 }
146             }else if(node.parent.right.key.equals(node.key)){
147                 if(node.right == null){
148                     node.parent.right = null;
149                 }else {
150                     node.parent.right = node.right;
151                     node.right.parent = node.parent;
152                 }
153 
154             }
155             return true;
156         }
157 
158         //被删除节点有两孩子
159         Node deleteNode = get(root , k);
160         Node minNode = get(root , getMin(deleteNode.right));
161         deleteNode.right.parent = deleteNode.left.parent = minNode;
162         if(deleteNode.parent == null){
163             if(minNode.key.equals(deleteNode.right.key)){
164                     minNode.left = deleteNode.left;
165                     root = minNode;
166                     deleteNode.left.parent = minNode;
167                     minNode.parent = null;
168             }else {
169                 if(minNode.right != null){
170                     minNode.right.parent = minNode.parent;
171                     minNode.parent.left = minNode.right;
172                 }
173                 minNode.right = deleteNode.right;
174                 minNode.left = deleteNode.left;
175                 deleteNode.right.parent = deleteNode.left.parent =  minNode;
176                 minNode.parent = null;
177                 root = minNode;
178             }
179 
180         }else {
181             if(minNode.key.equals(deleteNode.right.key)){
182                 minNode.left = deleteNode.left;
183                 minNode.parent = deleteNode.parent;
184                 deleteNode.left.parent = minNode;
185                 if(deleteNode.parent.right.key.equals(deleteNode.key)){
186                     deleteNode.parent.right = minNode;
187                 } else {
188                     deleteNode.parent.left = minNode;
189                 }
190             }else {
191                 minNode.right.parent = minNode.parent;
192                 minNode.parent.left = minNode.right;
193                 minNode.left = deleteNode.left;
194                 minNode.right = deleteNode.right;
195                 deleteNode.left.parent = deleteNode.right.parent = minNode;
196                 minNode.parent = deleteNode.parent;
197                 if(deleteNode.parent.left.key.equals(deleteNode.key)){
198 
199                     deleteNode.parent.left = minNode;
200                 }else {
201                     deleteNode.parent.right = minNode;
202                 }
203             }
204         }
205         return true;
206     }
207 
208     private K getMin(Node node){
209         if(node == null){
210             return null;
211         }
212         if(node.left == null){
213             return node.key;
214         }
215         return getMin(node.left);
216     }
217 
218     @Override
219     public String toString() {
220         Map<K,V> map = new HashMap<>();
221         setString(map,root);
222        return map.toString();
223     }
224 
225     private void setString(Map<K,V> map,Node node){
226         if(node != null){
227             map.put(node.key,node.value);
228         }
229         if(node.left != null){
230             setString(map,node.left);
231         }
232         if(node.right != null){
233             setString(map,node.right);
234         }
235     }
236 
237 
238 }

测试方法

 1 public class Test {
 2 
 3     public static void main(String[] args) {
 4 
 5         BinarySearchTree<String,String> b  = new BinarySearchTree<>();
 6         b.put("aaa","123");
 7         b.put("abc","85");
 8         b.put("trf","69");
 9         b.put("u","48");
10         b.put("jf","1");
11         b.put("dg","36");
12         b.put("aaa","999");
13         System.out.println(b.delete("aaa"));
14 
15         System.out.println(b);
16 
17     }
18 }

在执行delete前数据的模型为

删除 aaa后