使用AVL树实现Map

一、数组在裂变扩容时可能会出现环、在数组元素转为链表之后选择尾插法插入节点、数组到链表到AVL到RBT的转换

1、数组在裂变扩容时链表中的节点计算出来的位置可能也会发生变化，在多线程情况下调整节点位置可能会出现环。

2、数组中的数组元素转为链表后插入新节点时应选择采用尾插法，因为头插法在并发时可能会产生环（jdk1.7之前出现过这种问题）

3、数组------》链表（数组转为链表是为了充分利用内存空间）------》BST（AVL（缺点是在插入节点时需要大量调整））------》RBT

二、HashMap要实现的方法

1、put(K,V)：添加键值对

2、get(K)：根据键找对应的键值对

3、remove(K)：根据键移除对应的键值对

三、实现一棵树的底层有两种方式

1、数组法

浪费一些空间，找起来比较容易

2、节点法

节省空间、访问没有数组快

五、实现AVL树（节点、AVL）

1、节点：K和V，一对看，Pair(K,V)、height、left、right

2、AVLNode<K,V>：K、V是泛型，泛型就是不确定是什么类型

六、Car c = new Car()；这行代码在多线程环境下运行是否会出现问题

（1）线程的三大特性

原子性、可见性、有序性

（2） new Car()时发生了三件事

开辟内存空间、初始化对象、引用指向对象

（3）Car c = new Car()；这行代码在多线程环境下运行可能会出现对象未初始化异常

（4）解决方案：sychronized（同步锁）、Asychronized（异步锁）

（5）数据库中违背线程无序性的案例

在使用MyBatis框架时，使用SQL语句对数据库进行查询时查询出来的结果是使用Entity对其进行封装的，如果未创建代理对象，就直接对Entity进行访问，会违背线程无序性，出现错误

七、向AVL树中添加节点之后调整平衡的四种情况

1、情况一：LL型

解决方案：右旋

/*** 将当前节点右旋并返回新的节点* @param node 当前节点* @return 新节点*/private AVLNode<K,V> rightRotate(AVLNode<K,V> node){AVLNode<K,V> X = node.left;AVLNode<K,V> T2 = X.right;node.left = T2;X.right = node;// 更新X节点与node节点的高度X.height = Math.max(getHeight(X.left), getHeight(X.right)) + 1;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;return X;}

2、情况二：RR型

解决方案：左旋

/*** 将当前节点左旋并返回新的节点* @param node 当前节点* @return 新节点*/private AVLNode<K,V> leftRotate(AVLNode<K,V> node){AVLNode<K,V> X = node.right;AVLNode<K,V> T2 = X.left;node.right = T2;X.left = node;// 更新X节点与node节点的高度X.height = Math.max(getHeight(X.left), getHeight(X.right)) + 1;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;return X;}

3、情况三：LR型

解决方案：先左旋后右旋

// LR 先左旋后右旋if(bf > 1 && balanceFactor(node.left) <= 0){node.left = leftRotate(node.left);return rightRotate(node);}

4、情况四：RL型

解决方案：先右旋后左旋

if(bf < -1 && balanceFactor(node.right) >= 0){node.right = rightRotate(node.right);return leftRotate(node);}

八、从AVL树中删除节点的四种情况

1、情况一：删除节点的左子树和右子树都不为空

解决方案：用删除节点的右子树的最小节点替换掉删除节点

if(node.left != null && node.right != null){AVLNode<K,V> midNode = midNode(node.right);midNode.right = remove(node.right,midNode.pair.key);size ++;midNode.left = node.left;resultNode = midNode;}

2、情况二：删除节点的左节点为空右节点不为空

解决方案：将删除节点的右节点作为新节点

if(node.left == null && node.right != null){resultNode = node.right;}

3、情况三：删除节点的左节点不为空右节点为空

解决方案：将删除节点的左节点作为新节点

if(node.right == null && node.left != null){resultNode = node.left;}

4、情况四：删除节点的左右节点都不为空

解决方案：将null作为新节点

if(node.left == null && node.right == null){resultNode = null;
}

九、检查电脑上有多少行java源代码

public class StatisticsCodeCount {public static int count;public static void Statistics(File file) throws IOException {// 文件if(file.isFile()){if(file.getName().endsWith(".java")){BufferedReader reader = new BufferedReader(new FileReader(file));String line = null;while((line = reader.readLine()) != null){count++;}reader.close();}return;}// 文件夹File[] files = file.listFiles();if(files != null){for(File file1: files){Statistics(file1);}}}public static void main(String[] args) throws IOException {String path = "D:/";File file = new File(path);Statistics(file);System.out.println(StatisticsCodeCount.count*0.8);}
}

十、使用AVL树实现Map

package com.ffyc.avl;/*** 绑定key-value的对象* @param <K> key* @param <V> value*/
public class Pair<K extends Comparable<K>,V> {public K key;public V val;public Pair() {}public Pair(K key, V val) {this.key = key;this.val = val;}@Overridepublic String toString() {return "Pair{" +"key=" + key +", val=" + val +'}';}
}
package com.ffyc.avl;public class AVLNode <K extends Comparable<K>,V> {public int height;// 与节点不相关的，节点高度public Pair<K,V> pair;// 节点值public AVLNode<K,V> left;public AVLNode<K,V> right;public AVLNode() {}public AVLNode(Pair<K, V> pair) {this.pair = pair;this.height = 1;}public static void main(String[] args) {System.out.println(Math.cbrt(1000));}
}
package com.ffyc.avl;/*** AVL树* @param <K> key* @param <V> value*/
public class AVLTree <K extends Comparable<K>,V> {private int size;// 树中节点数目/*** 获取树中的节点数目* @return*/public int getSize(){return size;}/*** 获取当前节点的高度* @param node 当前节点* @return 高度*/private int getHeight(AVLNode<K,V> node){if(node == null) return 0;return node.height;}/*** 获取当前节点的平衡因子* @param node 当前节点* @return 平衡因子* bf > 1 不平衡 左子 >> 右子* bf < -1 不平衡 右子 << 左子* bf == 0 平衡* bf == 1 当前平衡* bf == -1 当前平衡*/private int balanceFactor(AVLNode<K,V> node){if(node == null) return 0;// 特殊处理return getHeight(node.left) - getHeight(node.right);}/*** 将当前节点右旋并返回新的节点* @param node 当前节点* @return 新节点*/private AVLNode<K,V> rightRotate(AVLNode<K,V> node){AVLNode<K,V> X = node.left;AVLNode<K,V> T2 = X.right;node.left = T2;X.right = node;// 更新X节点与node节点的高度X.height = Math.max(getHeight(X.left), getHeight(X.right)) + 1;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;return X;}/*** 将当前节点左旋并返回新的节点* @param node 当前节点* @return 新节点*/private AVLNode<K,V> leftRotate(AVLNode<K,V> node){AVLNode<K,V> X = node.right;AVLNode<K,V> T2 = X.left;node.right = T2;X.left = node;// 更新X节点与node节点的高度X.height = Math.max(getHeight(X.left), getHeight(X.right)) + 1;node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;return X;}/*** 在当前节点中插入值为pair的节点* @param node 当前节点* @param pair 节点值 key-value绑定对象* @return 插入新节点后的根节点*/public AVLNode<K,V> insert(AVLNode<K,V> node,Pair<K,V> pair){if(node == null){size++;return new AVLNode<>(pair);}// key相等，做数据更新if(pair.key.compareTo(node.pair.key) == 0){node.pair.val = pair.val;}else if(pair.key.compareTo(node.pair.key) < 0){node.left = insert(node.left, pair);}else{node.right = insert(node.right, pair);}// 更新node的高度node.height = Math.max(getHeight(node.left), getHeight(node.right)) + 1;// 计算node的平衡因子int bf = balanceFactor(node);// LL 右旋if(bf > 1 && balanceFactor(node.left) >= 0){return  rightRotate(node);}// RR 左旋if(bf < -1 && balanceFactor(node.right) <= 0){return leftRotate(node);}// LR 先左旋后右旋if(bf > 1 && balanceFactor(node.left) <= 0){node.left = leftRotate(node.left);return rightRotate(node);}// RL 先右旋后左旋if(bf < -1 && balanceFactor(node.right) >= 0){node.right = rightRotate(node.right);return leftRotate(node);}return node;}/*** 从当前节点中查询键为key的节点* @param node 当前节点* @param key 键* @return 键为key的节点*/public AVLNode<K,V> find(AVLNode<K,V> node, K key){if(node == null) return null;if(key.compareTo(node.pair.key) == 0){return  node;}else if(key.compareTo(node.pair.key) < 0){return find(node.left, key);}else{return find(node.right, key);}}/*** 获取当前节点的最小节点* @param node 当前节点* @return 最小节点*/private AVLNode<K,V> midNode(AVLNode<K,V> node){if(node == null) return null;while (node.left != null){node = node.left;}return node;}/*** 从当前节点中删除键为key的节点* @param node 当前节点* @param key* @return 新节点*/public AVLNode<K,V> remove(AVLNode<K,V> node, K key){if(node == null) return null;AVLNode<K,V> resultNode = null;if(key.compareTo(node.pair.key) == 0){// key找到了if(node.left == null){resultNode = node.right;}if(node.right == null){resultNode = node.left;}if(node.left != null && node.right != null){AVLNode<K,V> midNode = midNode(node.right);midNode.right = remove(node.right,midNode.pair.key);size ++;midNode.left = node.left;resultNode = midNode;}size --;}if(key.compareTo(node.pair.key) < 0){node.left = remove(node.left, key);resultNode = node;}if(key.compareTo(node.pair.key) > 0){node.right = remove(node.right, key);resultNode = node;}// 更新高度，调整平衡// 更新resultNode的高度if(resultNode != null){resultNode.height = Math.max(getHeight(resultNode.left), getHeight(resultNode.right)) + 1;// 计算node的平衡因子int bf = balanceFactor(resultNode);// LL 右旋if(bf > 1 && balanceFactor(resultNode.left) >= 0){return  rightRotate(resultNode);}// RR 左旋if(bf < -1 && balanceFactor(resultNode.right) <= 0){return leftRotate(resultNode);}// LR 先左旋后右旋if(bf > 1 && balanceFactor(resultNode.left) <= 0){resultNode.left = leftRotate(resultNode.left);return rightRotate(resultNode);}// RL 先右旋后左旋if(bf < -1 && balanceFactor(resultNode.right) >= 0){resultNode.right = rightRotate(resultNode.right);return leftRotate(resultNode);}}return resultNode;}
}
package com.ffyc.avl;public class TestAVL {public static void main(String[] args) {AVLTree<Integer,Integer> tree = new AVLTree<>();AVLNode<Integer,Integer> root = null;root = tree.insert(root, new Pair<>(1,15));root = tree.insert(root, new Pair<>(4,22));root = tree.insert(root, new Pair<>(2,11));root = tree.insert(root, new Pair<>(6,25));root = tree.insert(root, new Pair<>(6,99));System.out.println("树中节点的数量："+tree.getSize());root = tree.remove(root, 9);System.out.println("树中节点的数量："+tree.getSize());System.out.println(tree.find(root, 4));}
}