蓝鸟E4A做网站程序,网站设计 术语,泉州网站设计平台,计算机编程与网站建设AVL树又被叫做平衡二叉搜索树、平衡二叉树。AVL是其发明者的首字母缩写。
这篇文章中#xff0c;AVLTreeMap 类集成了 java.util.Map 接口#xff0c;并利用 AVL 树结构实现了 Map 接口的所有方法。本文还给出了测试代码。
为什么要发明AVL树#xff1f;
当我按照从小到大…AVL树又被叫做平衡二叉搜索树、平衡二叉树。AVL是其发明者的首字母缩写。
这篇文章中AVLTreeMap 类集成了 java.util.Map 接口并利用 AVL 树结构实现了 Map 接口的所有方法。本文还给出了测试代码。
为什么要发明AVL树
当我按照从小到大或者从大到小的顺序向二叉查找树插入节点二叉查找树就会退化成一个链表。这是二叉查找树的最差情况。搜索、插入、删除的最差效率都是 O(N)。这样就失去了用二叉查找树优化查找方法的意义。
就算不是最坏情况也会出现非常不平衡的树造成查找效率大于 O(logN) 小于 O(N) 。注意这里 logN 是以2为底N的对数。
AVL树的时间复杂度
因为含有数学公式就使用图片了。 代码实现
AVLTreeMap.java package zhangchao.avl;import java.util.*;/*** 利用AVL树也就是平衡二叉树来实现map* author zhangchao* param K 键* param V 值*/
public class AVLTreeMapK,V implements MapK, V{// 根节点private NodeK, V root null;private ComparatorK comparator;public AVLTreeMap(ComparatorK comparator) {this.comparator comparator;}Overridepublic int size() {if (null root) {return 0;}int size 0;// 当前层的节点列表ListNodeK, V currentLevel new ArrayList();currentLevel.add(root);while (!currentLevel.isEmpty()) {size currentLevel.size();// 下一层的节点列表ListNodeK, V nextLevel new ArrayList();for (NodeK, V tmpNode : currentLevel) {if (null ! tmpNode.leftChild) {nextLevel.add(tmpNode.leftChild);}if (null ! tmpNode.rightChild) {nextLevel.add(tmpNode.rightChild);}}currentLevel.clear();currentLevel.addAll(nextLevel);}return size;}Overridepublic boolean isEmpty() {return (null root);}Overridepublic boolean containsKey(Object keyObj) {if (null root) {return false;}K key (K)keyObj;NodeK, V current this.root;while(null ! current) {int compareResult this.comparator.compare(key, current.key);if (compareResult 0) {current current.leftChild;} else if (compareResult 0) {current current.rightChild;} else {return true;}}return false;}Overridepublic boolean containsValue(Object value) {if (null this.root) {return false;}ListNodeK, V nodeList this.nodeList();for (NodeK, V node : nodeList) {if (null value null node.value) {return true;}if (null ! value value.equals(node.value)) {return true;}}return false;}Overridepublic V get(Object keyObj) {if (null this.root) {return null;}K key (K)keyObj;NodeK, V current this.root;while(null ! current) {int compareResult this.comparator.compare(key, current.key);if (compareResult 0) {current current.leftChild;} else if (compareResult 0) {current current.rightChild;} else {return current.value;}}return null;}/*** 右旋操作* param parent 爷爷节点* param y 父级节点* param x 子级节点*/private void rotateRight(NodeK, V parent, NodeK, V y, NodeK, V x) {y.leftChild x.rightChild;x.rightChild y;if (null parent) {this.root x;} else {// 判断原来的y是parent的左子节点还是右子节点。if (null ! parent.leftChild 0 this.comparator.compare(parent.leftChild.key, y.key)) {parent.leftChild x;} else if (null ! parent.rightChild 0 this.comparator.compare(parent.rightChild.key, y.key)) {parent.rightChild x;}}y.height this.calHeight(y);x.height this.calHeight(x);if (null ! parent) {parent.height this.calHeight(parent);}}/*** 左旋操作* param parent 爷爷节点* param y 父级节点* param x 子级节点*/private void rotateLeft(NodeK, V parent, NodeK, V y, NodeK, V x) {y.rightChild x.leftChild;x.leftChild y;if (null parent) {this.root x;} else {// 判断原来的y是parent的左子节点还是右子节点。if (null ! parent.leftChild 0 this.comparator.compare(parent.leftChild.key, y.key)) {parent.leftChild x;} else if (null ! parent.rightChild 0 this.comparator.compare(parent.rightChild.key, y.key)) {parent.rightChild x;}}y.height this.calHeight(y);x.height this.calHeight(x);if (null ! parent) {parent.height this.calHeight(parent);}}Overridepublic V put(K key, V value) {if (null this.root) {this.root new Node();this.root.key key;this.root.value value;this.root.height 1;return null;}// 如果key是全新的保存所有的父亲节点。ListNodeK, V linkList new ArrayList();// 如果key是全新的这个变量是新节点的父亲节点。NodeK, V parent null;NodeK, V current root;int compareResult 0;while (null ! current) {compareResult this.comparator.compare(key, current.key);if (compareResult 0) {parent current;linkList.add(parent);current current.leftChild;} else if (compareResult 0) {parent current;linkList.add(parent);current current.rightChild;} else {// 有相等的key直接设置值就可以了。V oldValue current.value;current.value value;return oldValue;}}NodeK, V newItem new NodeK, V();newItem.key key;newItem.value value;newItem.height 1;if (compareResult 0) {parent.leftChild newItem;} else if (compareResult 0) {parent.rightChild newItem;}// 更新祖先节点的高度final int size linkList.size();for (int i size - 1; i 0; i--) {NodeK, V item linkList.get(i);item.height calHeight(item);}linkList.add(newItem);int parentSize linkList.size();for (int i parentSize - 1; i 0; i--) {// 当前节点NodeK, V z linkList.get(i);// z的父节点如果z是根节点那么就是null。NodeK, V z_parent null;if (i 0) {z_parent linkList.get(i - 1);}int leftHeight this.calHeight(z.leftChild);int rightHeight this.calHeight(z.rightChild);int balance leftHeight - rightHeight;if (balance 1) { // LL 或 LRNodeK, V y z.leftChild;NodeK, V x linkList.get(i 2);boolean isLL (null ! y.leftChild this.comparator.compare(y.leftChild.key, x.key) 0);boolean isLR (null ! y.rightChild this.comparator.compare(y.rightChild.key, x.key) 0);if (isLL) { // LL 右旋this.rotateRight(z_parent, z, y);}else if (isLR) { // LR// y和x之间左旋this.rotateLeft(z, y, x);// z和x之间右旋this.rotateRight(z_parent, z, x);}break; // 停止for循环} else if (balance -1) { // RR 或 RLNodeK, V y z.rightChild;NodeK, V x linkList.get(i 2);boolean isRR (null ! y.rightChild this.comparator.compare(y.rightChild.key, x.key) 0);boolean isRL (null ! y.leftChild this.comparator.compare(y.leftChild.key, x.key) 0);if (isRR) {this.rotateLeft(z_parent, z, y);} else if (isRL) {// y和x之间右旋this.rotateRight(z, y, x);// z和x之间左旋this.rotateLeft(z_parent, z, x);}break; // 停止for循环}}// 更新祖先节点高度for (int i parentSize - 1; i 0; i--) {NodeK, V item linkList.get(i);item.height calHeight(item);}return null;}private ListNodeK,V getNodeAndParent(K key, ListNodeK, V parents) {if (null this.root) {return null;}NodeK, V parent null;NodeK, V current this.root;while(null ! current) {int compareResult this.comparator.compare(key, current.key);if (compareResult 0) {parent current;if (null ! parents) {parents.add(parent);}current current.leftChild;} else if (compareResult 0) {parent current;if (null ! parents) {parents.add(parent);}current current.rightChild;} else {ListNodeK, V result new ArrayList();result.add(current);result.add(parent);return result;}}return null;}private K deleteAsBST(NodeK, V node, NodeK, V parent) {K endKey null;// 叶子节点if (null node.leftChild null node.rightChild) {if (node parent.leftChild) {parent.leftChild null;} else {parent.rightChild null;}return parent.key;}// 左子节点为空只有右子节点else if (null node.leftChild null ! node.rightChild) {if (node this.root) {this.root node.rightChild;} else if (node parent.leftChild) {parent.leftChild node.rightChild;} else if (node parent.rightChild) {parent.rightChild node.rightChild;}endKey node.rightChild.key;node.rightChild null;return endKey;}// else 包含两种情况// 1.左子节点不为空右子为空// 2.左子节点不为空右子不为空// 要删除的节点的左子树中找出最大节点。NodeK, V current node.leftChild;NodeK, V currentParent node;while (null ! current.rightChild) {currentParent current;current current.rightChild;}// 把current从原位置删除if (current currentParent.leftChild) {currentParent.leftChild current.leftChild;} else if (current currentParent.rightChild) {currentParent.rightChild current.leftChild;}// 让current取代node的位置if (node this.root) {this.root current;} else if (node parent.leftChild) {parent.leftChild current;} else {parent.rightChild current;}current.leftChild node.leftChild;current.rightChild node.rightChild;node.leftChild null;node.rightChild null;if (null current.leftChild) {return current.key;} else {NodeK, V p1 current.leftChild;while (null ! p1.rightChild) {p1 p1.rightChild;}return p1.key;}}Overridepublic V remove(Object keyObj) {// 空map不执行删除操作。if (null this.root) {return null;}K key (K)keyObj;// 只有根节点的情况if (null this.root.leftChild null this.root.rightChild) {if (this.comparator.compare(key ,this.root.key) 0) {V v this.root.value;this.root null;return v;} else {return null;}}// 不包含key就返回nullListNodeK, V nodeAndParent this.getNodeAndParent(key, new ArrayList());// map中没有对应的key不执行删除操作。if (null nodeAndParent || nodeAndParent.isEmpty()) {return null;}NodeK, V node nodeAndParent.get(0); // 要删除的节点V result node.value;NodeK, V parent nodeAndParent.get(1); // 要删除的节点的父亲节点// 按照二叉搜索树BST的方式删除节点。返回结束节点的键。K endKey this.deleteAsBST(node, parent);// 包含所有可能改动过高度的节点的列表。// 顺序是从根节点向下。// 替换了已删除节点位置的节点称为替换节点。// pathList的内容有以下三种情况// 1. 叶子节点pathList包含根节点到父节点。// 2. 没有左子节点只有右子节点pathList包含根节点到替换节点。// 3. 有左子节点pathList包含根节点到替换节点再加上替换节点到替换节点左子树最大节点。ListNodeK, V pathList new ArrayList();ListNodeK,V endKeyResult this.getNodeAndParent(endKey, pathList);pathList.add(endKeyResult.get(0));// 因为可能加入了节点所以要重新计算 parents 的长度int size pathList.size();for (int i size - 1; i 0; i--) {NodeK, V z_parent i 0 ? pathList.get(i - 1) : null;NodeK, V z pathList.get(i);// 更新高度z.height this.calHeight(z);if (null ! z_parent) {z_parent.height this.calHeight(z_parent);}int leftHeight calHeight(z.leftChild);int rightHeight calHeight(z.rightChild);int balance leftHeight - rightHeight;if (balance 1) {NodeK, V y z.leftChild;NodeK, V x null;int y_leftHeight calHeight(y.leftChild);int y_rightHeight calHeight(y.rightChild);if (y_leftHeight y_rightHeight) {// LLx y.leftChild;// z和y之间右旋this.rotateRight(z_parent, z, y);} else {// LRx y.rightChild;// y和x之间左旋this.rotateLeft(z, y, x);// z和x之间右旋this.rotateRight(z_parent, z, x);}} else if (balance -1) {NodeK, V y z.rightChild;NodeK, V x null;int y_leftHeight calHeight(y.leftChild);int y_rightHeight calHeight(y.rightChild);if (y_leftHeight y_rightHeight) {// RLx y.leftChild;// y和x之间右旋this.rotateRight(z, y, x);// z和x之间左旋this.rotateLeft(z_parent, z, x);} else {// RRx y.rightChild;// z和y之间左旋this.rotateLeft(z_parent, z, y);}}}return result;}// end public V remove(Object keyObj)Overridepublic void putAll(Map? extends K, ? extends V m) {if (null m) {return;}Set? extends K keySet m.keySet();for (K key : keySet) {this.put(key, m.get(key));}}Overridepublic void clear() {this.root null;}private ListNodeK, V nodeList() {if (null this.root) {return new ArrayListNodeK, V();}ListNodeK, V result new ArrayList();StackNodeK, V stack new Stack();NodeK, V current this.root;while(null ! current || !stack.isEmpty()) {while (null ! current) {stack.push(current);current current.leftChild;}current stack.pop();// 放入结果列表中result.add(current);current current.rightChild;}return result;}Overridepublic SetK keySet() {ListNodeK, V nodeList nodeList();SetK set new TreeSet(this.comparator);for (NodeK, V node : nodeList) {set.add(node.key);}return set;}Overridepublic CollectionV values() {ListNodeK, V nodeList nodeList();ListV result new ArrayList();for (NodeK,V node : nodeList) {result.add(node.value);}return result;}Overridepublic SetEntryK, V entrySet() {ListNodeK, V nodeList this.nodeList();SetEntryK, V set new TreeSetEntryK, V((o1, o2) - {NodeK, V n1 (NodeK, V) o1;NodeK, V n2 (NodeK, V) o2;return comparator.compare(n1.key, n2.key);});for (NodeK,V node : nodeList) {set.add(node);}return set;}private int calHeightForCheck(NodeK,V node) {if (null node) {return 0;}int height 0;ListNodeK,V currentLevel new ArrayList();currentLevel.add(node);while (!currentLevel.isEmpty()) {height ;ListNodeK,V nextLevel new ArrayList();for (NodeK,V tmpNode : currentLevel) {if (null ! tmpNode.leftChild) {nextLevel.add(tmpNode.leftChild);}if (null ! tmpNode.rightChild) {nextLevel.add(tmpNode.rightChild);}}currentLevel nextLevel;}return height;}private void showTree(Node node, Node parent, int level, String prefix) {if (null node) {return;}StringBuilder sb new StringBuilder();for (int i 0; i level; i) {sb.append( );}sb.append(prefix);sb.append(node.key).append( );if (parent ! null) {sb.append(parent.key);}int balance calHeightForCheck(node.leftChild) - calHeightForCheck(node.rightChild);sb.append( ).append(balance);System.out.println(sb);level;showTree(node.leftChild, node, level, left : );showTree(node.rightChild, node, level, right: );}/*** 打印树形结构。*/public void showTree() {if (null root) {System.out.println(null);}showTree(root, null, 0, root: );}private void checkTree(Node node, Node parent, int level) {if (null node) {return;}int balance calHeightForCheck(node.leftChild) - calHeightForCheck(node.rightChild);if (balance -1 || balance 1) {throw new RuntimeException(balance -1 || balance 1);}level;checkTree(node.leftChild, node, level);checkTree(node.rightChild, node, level);}/*** 检查树是不是符合AVL树的要求*/public void checkTree() {if (null root) {return;}checkTree(root, null, 0);}/*** 以node为根节点计算树的高度* param node 根节点* return 树的高度*/private int calHeight(NodeK,V node) {if (null node) {return 0;}int leftHeight (null node.leftChild) ? 0 : node.leftChild.height;int rightHeight (null node.rightChild) ? 0 : node.rightChild.height;return Math.max(leftHeight, rightHeight) 1;}class NodeK,V implements EntryK,V {K key null;V value null;int height;NodeK, V leftChild;NodeK, V rightChild;Overridepublic K getKey() {return key;}Overridepublic V getValue() {return value;}Overridepublic V setValue(V tmpValue) {V oldValue value;value tmpValue;return oldValue;}public int getHeight() {return height;}}
}
测试代码 TestAVLTreeMap.java 这里面有和二叉查找树Map的对比。 二叉查找树Map的实现文章https://blog.csdn.net/zhangchao19890805/article/details/128609922?spm1001.2014.3001.5502 package zhangchao.avl.test;import zhangchao.avl.AVLTreeMap;import zhangchao.bst.BstTreeMap;import java.util.*;public class TestAVLTreeMap {public static void main(String[] args) {t7();}public static void t7() {int a[] {20, 10, 21, 22, 5, 15, 1};ComparatorInteger comparator (o1, o2) -{if (null o1 null o2) {return 0;}if (null o1 null ! o2) {return -1;}if (null ! o1 null o2) {return 1;}return o1 - o2;};AVLTreeMapInteger, String avlTreeMap new AVLTreeMap(comparator );for (int key : a) {avlTreeMap.put(key, __ key);}avlTreeMap.showTree();avlTreeMap.remove(20);System.out.println(\n);avlTreeMap.showTree();avlTreeMap.checkTree();}public static void t6() {ComparatorInteger comparator (o1, o2) -{if (null o1 null o2) {return 0;}if (null o1 null ! o2) {return -1;}if (null ! o1 null o2) {return 1;}return o1 - o2;};AVLTreeMapInteger, String avlTreeMap new AVLTreeMap(comparator );BstTreeMapInteger, String bstTreeMap new BstTreeMap(comparator);long t1;long t2;// 比对插入System.out.println(insert);Random r new Random();final int MAX 100000;ListInteger list new ArrayList();for (int i 0; i MAX; i) {int key r.nextInt(MAX);list.add(i);}t1 System.currentTimeMillis();for (int key : list) {avlTreeMap.put(key, __ key);}t2 System.currentTimeMillis();System.out.println(AVL: (t2 - t1));t1 System.currentTimeMillis();for (int key : list) {bstTreeMap.put(key, __ key);}t2 System.currentTimeMillis();System.out.println(BST: (t2 - t1));// 比对查询System.out.println(\nsearch);t1 System.currentTimeMillis();for (int i 0; i MAX; i) {avlTreeMap.get(i);}t2 System.currentTimeMillis();System.out.println(AVL: (t2 - t1));t1 System.currentTimeMillis();for (int i 0; i MAX; i) {bstTreeMap.get(i);}t2 System.currentTimeMillis();System.out.println(BST: (t2 - t1));
// avlTreeMap.showTree();// 比对删除System.out.println(\nremove);t1 System.currentTimeMillis();Collections.shuffle(list);for (int key : list) {avlTreeMap.remove(key);}t2 System.currentTimeMillis();System.out.println(AVL: (t2 - t1));t1 System.currentTimeMillis();for (int key : list) {bstTreeMap.remove(key);}t2 System.currentTimeMillis();System.out.println(BST: (t2 - t1));avlTreeMap.checkTree();}public static void t3() {MapInteger, String map new AVLTreeMap( (o1, o2) -{if (null o1 null o2) {return 0;}if (null o1 null ! o2) {return -1;}if (null ! o1 null o2) {return 1;}return o1 - o2;});int[] arr new int[]{20,10,21,5,15,22,13,16};for (int i : arr) {map.put(i, __ String.valueOf(i));}AVLTreeMap avlTreeMap (AVLTreeMap) map;avlTreeMap.showTree();avlTreeMap.remove(10);System.out.println(\n);avlTreeMap.showTree();avlTreeMap.checkTree();}public static void t2() {MapInteger, String map new AVLTreeMap( (o1, o2) -{if (null o1 null o2) {return 0;}if (null o1 null ! o2) {return -1;}if (null ! o1 null o2) {return 1;}return o1 - o2;});int[] arr new int[]{8,3,6,1,2,98,2,6,150,170,160,7,52,28,75,14,40,86,10,21,46,25};for (int i : arr) {map.put(i, __ String.valueOf(i));}AVLTreeMap avlTreeMap (AVLTreeMap) map;avlTreeMap.showTree();avlTreeMap.remove(7);System.out.println(\n\n\n);avlTreeMap.showTree();avlTreeMap.checkTree();}public static void t1() {MapInteger, String map new AVLTreeMap( (o1, o2) -{if (null o1 null o2) {return 0;}if (null o1 null ! o2) {return -1;}if (null ! o1 null o2) {return 1;}return o1 - o2;});int[] arr new int[]{8,3,6,1,2,98,2,6,150,170,160,7,52,28,75,14,40,86,10,21,46,25};for (int i : arr) {map.put(i, __ String.valueOf(i));}AVLTreeMap avlTreeMap (AVLTreeMap) map;avlTreeMap.showTree();System.out.println(map.get(3));System.out.println(map.get(6));System.out.println(map.get(98));System.out.println(map.get(null));SetInteger set avlTreeMap.keySet();for (Integer i : set) {System.out.println(i);}System.out.println();HashSetInteger hashSet new HashSet();for (int i : arr) {hashSet.add(i);}for (int i : hashSet) {if (!set.contains(i)) {System.out.println(false);}}System.out.println(set.size() hashSet.size());System.out.println(containsKey 3: avlTreeMap.containsKey(3));System.out.println(containsKey 4: avlTreeMap.containsKey(4));System.out.println(containsValue __3: avlTreeMap.containsValue(__3));System.out.println(containsValue __4: avlTreeMap.containsValue(__4));System.out.println();SetMap.EntryInteger, String entrySet avlTreeMap.entrySet();for (Map.EntryInteger, String item : entrySet) {System.out.println(item.getKey() : item.getValue());}avlTreeMap.checkTree();}
}
