平衡二叉树：对于任意一个节点，左子树和右子树的高度差不能超过1
1package Date_pacage; 2import java.util.ArrayList; 3 4public class AVLTree<K extends Comparable<K>, V> { 5 6 private class Node{ 7 public K key; 8 public V value; 9 public Node left, right; 10 public int height; 11 12 public Node(K key, V value){ 13 this.key = key; 14 this.value = value; 15 left = null; 16 right = null; 17 height = 1; 18 } 19 } 20 21 private Node root; 22 private int size; 23 24 public AVLTree(){ 25 root = null; 26 size = 0; 27 } 28 29 public int getSize(){ 30 return size; 31 } 32 33 public boolean isEmpty(){ 34 return size == 0; 35 } 36 37 // 判断该二叉树是否是一棵二分搜索树 38 public boolean isBST(){ 39 40 ArrayList<K> keys = new ArrayList<>(); 41 inOrder(root, keys); 42 for(int i = 1 ; i < keys.size() ; i ++) 43 if(keys.get(i - 1).compareTo(keys.get(i)) > 0) 44 return false; 45 return true; 46 } 47 48 private void inOrder(Node node, ArrayList<K> keys){ 49 50 if(node == null) 51 return; 52 53 inOrder(node.left, keys); 54 keys.add(node.key); 55 inOrder(node.right, keys); 56 } 57 58 // 判断该二叉树是否是一棵平衡二叉树 59 public boolean isBalanced(){ 60 return isBalanced(root); 61 } 62 63 // 判断以Node为根的二叉树是否是一棵平衡二叉树，递归算法 64 private boolean isBalanced(Node node){ 65 66 if(node == null) 67 return true; 68 69 int balanceFactor = getBalanceFactor(node); 70 if(Math.abs(balanceFactor) > 1) 71 return false; 72 return isBalanced(node.left) && isBalanced(node.right); 73 } 74 75 // 获得节点node的高度 76 private int getHeight(Node node){ 77 if(node == null) 78 return 0; 79 return node.height; 80 } 81 82 // 获得节点node的平衡因子 83 private int getBalanceFactor(Node node){ 84 if(node == null) 85 return 0; 86 return getHeight(node.left) - getHeight(node.right); 87 } 88 89 // 对节点y进行向右旋转操作，返回旋转后新的根节点x 90 // y x 91 // / \ / \ 92 // x T4 向右旋转 (y) z y 93 // / \ - - - - - - - -> / \ / \ 94 // z T3 T1 T2 T3 T4 95 // / \ 96 // T1 T2 97 private Node rightRotate(Node y) { 98 Node x = y.left; 99 Node T3 = x.right; 100 101 // 向右旋转过程 102 x.right = y; 103 y.left = T3; 104 105 // 更新height 106 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; 107 x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; 108 109 return x; 110 } 111 112 // 对节点y进行向左旋转操作，返回旋转后新的根节点x 113 // y x 114 // / \ / \ 115 // T1 x 向左旋转 (y) y z 116 // / \ - - - - - - - -> / \ / \ 117 // T2 z T1 T2 T3 T4 118 // / \ 119 // T3 T4 120 private Node leftRotate(Node y) { 121 Node x = y.right; 122 Node T2 = x.left; 123 124 // 向左旋转过程 125 x.left = y; 126 y.right = T2; 127 128 // 更新height 129 y.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1; 130 x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1; 131 132 return x; 133 } 134 135 // 向二分搜索树中添加新的元素(key, value) 136 public void add(K key, V value){ 137 root = add(root, key, value); 138 } 139 140 // 向以node为根的二分搜索树中插入元素(key, value)，递归算法 141 // 返回插入新节点后二分搜索树的根 142 private Node add(Node node, K key, V value){ 143 144 if(node == null){ 145 size ++; 146 return new Node(key, value); 147 } 148 149 if(key.compareTo(node.key) < 0) 150 node.left = add(node.left, key, value); 151 else if(key.compareTo(node.key) > 0) 152 node.right = add(node.right, key, value); 153 else // key.compareTo(node.key) == 0 154 node.value = value; 155 156 // 更新height 157 node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right)); 158 159 // 计算平衡因子 160 int balanceFactor = getBalanceFactor(node); 161 162 // 平衡维护 163 // LL 164 if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) 165 return rightRotate(node); 166 167 // RR 168 if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) 169 return leftRotate(node); 170 171 // LR 172 if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) { 173 node.left = leftRotate(node.left); 174 return rightRotate(node); 175 } 176 177 // RL 178 if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) { 179 node.right = rightRotate(node.right); 180 return leftRotate(node); 181 } 182 183 return node; 184 } 185 186 // 返回以node为根节点的二分搜索树中，key所在的节点 187 private Node getNode(Node node, K key){ 188 189 if(node == null) 190 return null; 191 192 if(key.equals(node.key)) 193 return node; 194 else if(key.compareTo(node.key) < 0) 195 return getNode(node.left, key); 196 else // if(key.compareTo(node.key) > 0) 197 return getNode(node.right, key); 198 } 199 200 public boolean contains(K key){ 201 return getNode(root, key) != null; 202 } 203 204 public V get(K key){ 205 206 Node node = getNode(root, key); 207 return node == null ? null : node.value; 208 } 209 210 public void set(K key, V newValue){ 211 Node node = getNode(root, key); 212 if(node == null) 213 throw new IllegalArgumentException(key + " doesn't exist!"); 214 215 node.value = newValue; 216 } 217 218 // 返回以node为根的二分搜索树的最小值所在的节点 219 private Node minimum(Node node){ 220 if(node.left == null) 221 return node; 222 return minimum(node.left); 223 } 224 225 // 从二分搜索树中删除键为key的节点 226 public V remove(K key){ 227 228 Node node = getNode(root, key); 229 if(node != null){ 230 root = remove(root, key); 231 return node.value; 232 } 233 return null; 234 } 235 236 private Node remove(Node node, K key){ 237 238 if( node == null ) 239 return null; 240 241 Node retNode; 242 if( key.compareTo(node.key) < 0 ){ 243 node.left = remove(node.left , key); 244 // return node; 245 retNode = node; 246 } 247 else if(key.compareTo(node.key) > 0 ){ 248 node.right = remove(node.right, key); 249 // return node; 250 retNode = node; 251 } 252 else{ // key.compareTo(node.key) == 0 253 254 // 待删除节点左子树为空的情况 255 if(node.left == null){ 256 Node rightNode = node.right; 257 node.right = null; 258 size --; 259 // return rightNode; 260 retNode = rightNode; 261 } 262 263 // 待删除节点右子树为空的情况 264 else if(node.right == null){ 265 Node leftNode = node.left; 266 node.left = null; 267 size --; 268 // return leftNode; 269 retNode = leftNode; 270 } 271 272 // 待删除节点左右子树均不为空的情况 273 else{ 274 // 找到比待删除节点大的最小节点, 即待删除节点右子树的最小节点 275 // 用这个节点顶替待删除节点的位置 276 Node successor = minimum(node.right); 277 //successor.right = removeMin(node.right); 278 successor.right = remove(node.right, successor.key); 279 successor.left = node.left; 280 281 node.left = node.right = null; 282 283 // return successor; 284 retNode = successor; 285 } 286 } 287 288 if(retNode == null) 289 return null; 290 291 // 更新height 292 retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right)); 293 294 // 计算平衡因子 295 int balanceFactor = getBalanceFactor(retNode); 296 297 // 平衡维护 298 // LL 299 if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) 300 return rightRotate(retNode); 301 302 // RR 303 if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) 304 return leftRotate(retNode); 305 306 // LR 307 if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) { 308 retNode.left = leftRotate(retNode.left); 309 return rightRotate(retNode); 310 } 311 312 // RL 313 if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) { 314 retNode.right = rightRotate(retNode.right); 315 return leftRotate(retNode); 316 } 317 318 return retNode; 319 } 320 321 322}
AVLMap
1package Date_pacage; 2 3public class AVLMap<K extends Comparable<K>,V> implements Map<K, V> { 4 private AVLTree<K, V> avl; 5 6 public AVLMap(){ 7 avl = new AVLTree<>(); 8 } 9 10 @Override 11 public void add(K key, V value) { 12 // TODO Auto-generated method stub 13 avl.add(key, value); 14 } 15 16 @Override 17 public V remove(K key) { 18 // TODO Auto-generated method stub 19 return avl.remove(key); 20 } 21 22 @Override 23 public boolean contains(K key) { 24 // TODO Auto-generated method stub 25 return avl.contains(key); 26 } 27 28 @Override 29 public V get(K key) { 30 // TODO Auto-generated method stub 31 return avl.get(key); 32 } 33 34 @Override 35 public void set(K key, V newValue) { 36 // TODO Auto-generated method stub 37 avl.set(key, newValue); 38 } 39 40 @Override 41 public int getSize() { 42 // TODO Auto-generated method stub 43 return avl.getSize(); 44 } 45 46 @Override 47 public boolean inEmpty() { 48 // TODO Auto-generated method stub 49 return avl.isEmpty(); 50 } 51}
AVLSet：
1package Date_pacage; 2 3public class AVLSet<E extends Comparable<E>> implements Set<E> { 4 5 private AVLTree<E, Object> avl; 6 7 public AVLSet() { 8 avl = new AVLTree<>(); 9 } 10 11 @Override 12 public void add(E e) { 13 // TODO Auto-generated method stub 14 avl.add(e, null); 15 } 16 17 @Override 18 public void remove(E e) { 19 // TODO Auto-generated method stub 20 avl.remove(e); 21 } 22 23 @Override 24 public boolean contains(E e) { 25 // TODO Auto-generated method stub 26 return avl.contains(e); 27 } 28 29 @Override 30 public int getSize() { 31 // TODO Auto-generated method stub 32 return avl.getSize(); 33 } 34 35 @Override 36 public boolean isEmpty() { 37 // TODO Auto-generated method stub 38 return avl.isEmpty(); 39 } 40 41}