数据结构-高层数据结构：映射/字典（Map）【有序字典：基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典：基于哈希表】

2024-09-02 03:18
文章标签 二叉树 链表 数据结构 搜索 二分 有序 哈希 红黑树 平衡 map 字典 映射 无序 高层

本文主要是介绍数据结构-高层数据结构：映射/字典（Map）【有序字典：基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典：基于哈希表】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述
在这里插入图片描述

在这里插入图片描述
在这里插入图片描述

Map.java

package map;/*** 映射*/
public interface Map<K,V> {/*** 添加元素** @param key* @param value* @return void*/void add(K key,V value);/*** 删除元素** @param key* @return V*/V remove(K key);/*** 查看是否包含某个key** @param key* @return boolean*/boolean contains(K key);/*** 获取某个key对应的value** @param key* @return V*/V get(K key);/*** 更新某个key对应的value** @param key* @param value* @return void*/void set(K key ,V value);/*** 获取大小** @param* @return int*/int getSize();/*** 查看是否为空** @param* @return boolean*/boolean isEmpty();
}

一、基于二分搜索树的Map

BinarySearchTreeMap.java

package map;/*** 利用二分搜索树实现映射** @version 2018/8/19*/
public class BinarySearchTreeMap<K extends Comparable<K>,V> implements Map<K,V> {private Node root;private int size;public BinarySearchTreeMap() {root = null;size = 0;}@Overridepublic void add(K key, V value) {root = add(root,key,value);}/*** 向node为根元素的二分搜索树中插入元素* 递归算法** @param node* @param key* @param value* @return void*/private Node add(Node node, K key, V value){//递归终止条件，返回结果为nullif(node == null){size ++;return new Node(key,value);}if(key.compareTo(node.key) < 0){node.left = add(node.left,key,value);}else if(key.compareTo(node.key) > 0){node.right = add(node.right,key,value);}else {node.value = value;}return node;}/*** 查找二分搜索树的最小值** @param* @return V* @version 2018/8/18*/public V minimum(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return minimum(root).value;}/*** 查找以node为根节点二分搜索树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node minimum(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.left == null){return node;}return minimum(node.left);}/*** 查找二分搜索树的最大值** @param* @return V* @version 2018/8/18*/public V maximize(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return maximize(root).value;}/*** 查找以node为根节点二分搜索树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node maximize(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.right == null){return node;}return minimum(node.right);}/*** 删除二分搜索树的最大值** @param* @return V* @version 2018/8/18*/public V removeMax(){V maximize = maximize();removeMax(root);return maximize;}/*** 删除以node为根的二分搜索树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMin(node.right);return node;}/*** 删除二分搜索树的最小值** @param* @return BinarySearchTree<E>.Node* @version 2018/8/18*/public V removeMin(){V minimum = minimum();removeMin(root);return minimum;}/*** 删除以node为根的二分搜索树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}@Overridepublic V remove(K key) {Node node = getNode(root,key);if(node != null){root = remove(root, key);return node.value;}return null;}/*** 删除以node为根的二分搜索树中的指定元素* 深度优先遍历，递归实现** @param node* @param key* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node remove(Node node, K key) {if(node == null){return null;}if(key.compareTo(node.key) < 0){node.left = remove(node.left,key);return node;}else if(key.compareTo(node.key) > 0){node.right = remove(node.right,key);return node;}else /*if(key.compareTo(node.key) == 0)*/{// 删除右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 删除左子树为空的情况else if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 删除左子树、右子树均不为空的情况else {// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)// 获得后继节点Node successor = minimum(node.right);// 删除后继节点，并让待删除节点的右子树成为后继节点的右子树successor.right = removeMin(node);// 让待删除节点的左子树成为后继节点的左子树successor.left = node.left;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return successor;/**// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)// 获得前驱节点Node predecessor = maximize(node.left);// 删除前驱节点，并让待删除节点的左子树成为前驱节点的左子树predecessor.left = removeMax(node);// 让待删除节点的右子树成为前驱节点的右子树predecessor.right = node.right;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return predecessor;*/}}}@Overridepublic boolean contains(K key) {return getNode(root,key) != null;}@Overridepublic V get(K key) {Node node = getNode(root, key);return node != null ? node.value : null;}@Overridepublic void set(K key, V value) {Node node = getNode(root, key);if(node == null){throw new IllegalArgumentException("Set failed. key is not exists!");}node.value = value;}@Overridepublic int getSize() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}/*** 根据key获取Node** @param node* @param key* @return map.LinkedListMap<K,V>.Node*/public Node getNode(Node node,K key){if(node == null){return null;}if(key.compareTo(node.key) == 0){return node;}else if(key.compareTo(node.key) < 0){return getNode(node.left,key);}else{return getNode(node.right,key);}}/*** 节点类** @version 2018/8/18*/private class Node{public K key;public V value;public Node left,right;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;}}
}

二、基于平衡二叉树的Map

AVLTree.java

package map;import set.FileOperation;import java.util.ArrayList;/*** AVL平衡二叉树** @version 2018/9/1*/
public class AVLTree<K extends Comparable<K>,V> {private Node root;private int size;public AVLTree() {root = null;size = 0;}/*** 获取某个节点的高度** @param node* @return int* @version 2018/9/1*/private int getHeight(Node node){if(node == null){return 0;}return node.height;}/*** 获取某个节点的平衡因子** @param node* @return int* @version 2018/9/1*/private int getBalanceFactor(Node node){if (node == null) {return 0;}return getHeight(node.left) - getHeight(node.right);}/*** 查看AVL平衡二叉树是否是二分搜索树** @param* @return boolean* @version 2018/9/1*/private boolean isBinarySearchTree(){ArrayList<K> keys = new ArrayList<>();inOrder(root,keys);for (int i = 1; i < keys.size(); i++) {if(keys.get(i - 1).compareTo(keys.get(i)) > 0){return false;}}return true;}/*** 查看AVL平衡二叉树是否是平衡二叉树** @return boolean* @version 2018/9/1*/private boolean isBalanced(){return isBalanced(root);}/*** 递归查看以node为根节点的AVL平衡二叉树是否是平衡二叉树** @param node* @return boolean* @version 2018/9/1*/private boolean isBalanced(Node node){if (node == null) {return true;}int balanceFactor = getBalanceFactor(node);if(Math.abs(balanceFactor) > 1){return false;}return isBalanced(node.left) && isBalanced(node.right);}// 对节点y进行向右旋转操作，返回旋转后新的根节点x//        y                              x//       / \                           /   \//      x   T4     向右旋转 (y)        z     y//     / \       - - - - - - - ->    / \   / \//    z   T3                       T1  T2 T3 T4//   / \// T1   T2/*** 右旋转操作* @param y* @return AVLTree<K,V>.Node* @version 2018/9/1*/private Node rightRotate(Node y){Node x = y.left;Node T3 = x.right;//右旋转操作x.right = y;y.left = T3;//更新heighty.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}// 对节点y进行向左旋转操作，返回旋转后新的根节点x//    y                             x//  /  \                          /   \// T1   x      向左旋转 (y)       y     z//     / \   - - - - - - - ->   / \   / \//   T2  z                     T1 T2 T3 T4//      / \//     T3 T4/*** 左旋转操作** @param y* @return AVLTree<K,V>.Node* @version 2018/9/1*/private Node leftRotate(Node y){Node x = y.right;Node T2 = x.left;//左旋转操作x.left = y;y.right = T2;//更新heighty.height = Math.max(getHeight(y.left), getHeight(y.right)) + 1;x.height = Math.max(getHeight(x.left), getHeight(x.right)) + 1;return x;}/*** 中序遍历以node为根节点的AVL平衡二叉树* 深度优先遍历，递归实现** @param node* @return void* @version 2018/8/18*/private void inOrder(Node node, ArrayList<K> keys){if(node == null){return;}inOrder(node.left,keys);keys.add(node.key);inOrder(node.right,keys);}/*** 向AVL平衡二叉树中插入元素** @param key* @param value* @return void* @version 2018/9/1*/public void add(K key, V value) {root = add(root,key,value);}/*** 向node为根元素的AVL平衡二叉树中插入元素* 递归算法** @param node* @param key* @param value* @return void*/private Node add(Node node, K key, V value){//递归终止条件，返回结果为nullif(node == null){size ++;return new Node(key,value);}if(key.compareTo(node.key) < 0){node.left = add(node.left,key,value);}else if(key.compareTo(node.key) > 0){node.right = add(node.right,key,value);}else {node.value = value;}/**========== 维护平衡 Start ==========*///更新Heightnode.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));//计算平衡因子int balanceFactor = getBalanceFactor(node);//LL左孩子节点的左侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(node.left) >= 0){//右旋转操作return rightRotate(node);}//RR右孩子节点的右侧产生不平衡if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0){//左旋转操作return leftRotate(node);}//LR左孩子节点的右侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(node.left) < 0){node.left = leftRotate(node.left);//右旋转操作return rightRotate(node);}//RL右孩子节点的左侧产生不平衡if(balanceFactor <-1 && getBalanceFactor(node.right) > 0){node.right = rightRotate(node.right);//右旋转操作return leftRotate(node);}/**========== 维护平衡 End ==========*/return node;}/*** 查找AVL平衡二叉树的最小值** @param* @return V* @version 2018/8/18*/public V minimum(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return minimum(root).value;}/*** 查找以node为根节点AVL平衡二叉树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node minimum(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.left == null){return node;}return minimum(node.left);}/*** 查找AVL平衡二叉树的最大值** @param* @return V* @version 2018/8/18*/public V maximize(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return maximize(root).value;}/*** 查找以node为根节点AVL平衡二叉树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node maximize(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.right == null){return node;}return minimum(node.right);}/*** 删除AVL平衡二叉树的最大值** @param* @return V* @version 2018/8/18*/public V removeMax(){V maximize = maximize();removeMax(root);return maximize;}/*** 删除以node为根的AVL平衡二叉树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMin(node.right);return node;}/*** 删除AVL平衡二叉树的最小值** @param* @return BinarySearchTree<E>.Node* @version 2018/8/18*/public V removeMin(){V minimum = minimum();removeMin(root);return minimum;}/*** 删除以node为根的AVL平衡二叉树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}public V remove(K key) {Node node = getNode(root,key);if(node != null){root = remove(root, key);return node.value;}return null;}/*** 删除以node为根的AVL平衡二叉树中的指定元素* 深度优先遍历，递归实现** @param node* @param key* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node remove(Node node, K key) {if(node == null){return null;}Node resultNode;if(key.compareTo(node.key) < 0){node.left = remove(node.left, key);resultNode = node;}else if(key.compareTo(node.key) > 0){node.right = remove(node.right, key);resultNode = node;}else /*if(key.compareTo(node.key) == 0)*/{// 删除右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;resultNode = leftNode;}// 删除左子树为空的情况else if(node.left == null){Node rightNode = node.right;node.right = null;size --;resultNode = rightNode;}// 删除左子树、右子树均不为空的情况else {// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)// 获得后继节点Node successor = minimum(node.right);// 删除后继节点，并让待删除节点的右子树成为后继节点的右子树successor.right = remove(node.right,successor.key);// 让待删除节点的左子树成为后继节点的左子树successor.left = node.left;// 将待删除节点的左、右子节点置为空node.left = node.right = null;resultNode = successor;/**// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)// 获得前驱节点Node predecessor = maximize(node.left);// 删除前驱节点，并让待删除节点的左子树成为前驱节点的左子树predecessor.left = removeMax(node);// 让待删除节点的右子树成为前驱节点的右子树predecessor.right = node.right;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return predecessor;*/}}/**========== 维护平衡 Start ==========*/if(resultNode == null){return null;}//更新HeightresultNode.height = 1 + Math.max(getHeight(resultNode.left), getHeight(resultNode.right));//计算平衡因子int balanceFactor = getBalanceFactor(resultNode);//LL左孩子节点的左侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(resultNode.left) >= 0){//右旋转操作return rightRotate(resultNode);}//RR右孩子节点的右侧产生不平衡if (balanceFactor < -1 && getBalanceFactor(resultNode.right) <= 0){//左旋转操作return leftRotate(resultNode);}//LR左孩子节点的右侧产生不平衡if(balanceFactor > 1 && getBalanceFactor(resultNode.left) < 0){resultNode.left = leftRotate(resultNode.left);//右旋转操作return rightRotate(resultNode);}//RL右孩子节点的左侧产生不平衡if(balanceFactor <-1 && getBalanceFactor(resultNode.right) > 0){resultNode.right = rightRotate(resultNode.right);//右旋转操作return leftRotate(resultNode);}/**========== 维护平衡 End ==========*/return resultNode;}public boolean contains(K key) {return getNode(root,key) != null;}public V get(K key) {Node node = getNode(root, key);return node != null ? node.value : null;}public void set(K key, V value) {Node node = getNode(root, key);if(node == null){throw new IllegalArgumentException("Set failed. key is not exists!");}node.value = value;}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}/*** 根据key获取Node** @param node* @param key* @return map.LinkedListMap<K,V>.Node*/public Node getNode(Node node,K key){if(node == null){return null;}if(key.compareTo(node.key) == 0){return node;}else if(key.compareTo(node.key) < 0){return getNode(node.left,key);}else{return getNode(node.right,key);}}/*** 节点类** @version 2018/8/18*/private class Node{public K key;public V value;public Node left,right;public int height;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;height = 1;}}public static void main(String[] args) {ArrayList<String> words = new ArrayList<>();FileOperation.readFile("D:\\iProgramming\\Projects\\IntelliJ IDEA\\Play-with-Data-Structures-Ronglexie\\12-AVL-Tree\\src\\pride-and-prejudice.txt",words);System.out.println("Total words: " + words.size());AVLTree<String,Integer> wordsMap = new AVLTree();for (String word : words) {if(wordsMap.contains(word)){wordsMap.set(word,wordsMap.get(word)+1);}else {wordsMap.add(word,1);}}System.out.println("Total different words: " + wordsMap.getSize());System.out.println("Frequency of PRIDE "+wordsMap.get("pride"));System.out.println("Frequency of is "+wordsMap.get("is"));System.out.println("Frequency of of "+wordsMap.get("of"));System.out.println("isBinarySearchTree:"+wordsMap.isBinarySearchTree());System.out.println("isBalanced:"+wordsMap.isBalanced());for (String word : words) {wordsMap.remove(word);if(!wordsMap.isBinarySearchTree() || !wordsMap.isBalanced()){throw new RuntimeException("Error");}}}
}

AVLTreeMap.java

package map;/*** 利用AVL平衡二叉树实现映射** @version 2018/9/1*/
public class AVLTreeMap<K extends Comparable<K>,V> implements Map<K,V> {AVLTree<K,V> avlTree;public AVLTreeMap() {avlTree = new AVLTree();}@Overridepublic void add(K key, V value) {avlTree.add(key, value);}@Overridepublic V remove(K key) {return avlTree.remove(key);}@Overridepublic boolean contains(K key) {return avlTree.contains(key);}@Overridepublic V get(K key) {return avlTree.get(key);}@Overridepublic void set(K key, V value) {avlTree.set(key, value);}@Overridepublic int getSize() {return avlTree.getSize();}@Overridepublic boolean isEmpty() {return avlTree.isEmpty();}
}

三、基于红黑树的Map

RedBlackTree.java

package map;/*** 红黑树** @version 2018/9/2*/
public class RedBlackTree<K extends Comparable<K>,V> {public static final boolean RED = true;public static final boolean BLACK = false;private Node root;private int size;public RedBlackTree() {root = null;size = 0;}/*** 左旋转** @param node* @return RedBlackTree<K,V>.Node* @version 2018/9/2*///   node                     x//  /   \     左旋转         /  \// T1   x   --------->   node   T3//     / \              /   \//    T2 T3            T1   T2private Node leftRotate(Node node){Node x = node.right;//左旋转操作node.right = x.left;x.left = node;x.color = node.color;node.color = RED;return x;}/*** 颜色翻转** @param node* @return void* @version 2018/9/2*/private void flipColors(Node node){node.color = RED;node.left.color = BLACK;node.right.color = BLACK;}/*** 右旋转** @param node* @return RedBlackTree<K,V>.Node* @version 2018/9/2*///     node                   x//    /   \     右旋转       /  \//   x    T2   ------->   y   node//  / \                       /  \// y  T1                     T1  T2private Node rightRotate(Node node){Node x = node.left;//右旋转操作node.left = x.right;x.right = node;x.color = node.color;node.color = RED;return x;}/*** 判断当前节点是否为红色** @param node* @return boolean* @version 2018/9/2*/public boolean isRed(Node node) {if(node == null){return BLACK;}return node.color;}/*** 向红黑树中插入元素* * @param key* @param value* @return void* @version 2018/9/2*/public void add(K key, V value) {root = add(root,key,value);root.color = BLACK;//根节点为黑色节点}/*** 向node为根元素的红黑树中插入元素* 递归算法** @param node* @param key* @param value* @return void*/private Node add(Node node, K key, V value){//递归终止条件，返回结果为nullif(node == null){size ++;return new Node(key,value);}if(key.compareTo(node.key) < 0){node.left = add(node.left,key,value);}else if(key.compareTo(node.key) > 0){node.right = add(node.right,key,value);}else {node.value = value;}/**==========维护红黑树性质 Start==========*///判断是否需要左旋转if(isRed(node.right) && !isRed(node.left)){node = leftRotate(node);}//判断是否需要右旋转if(isRed(node.left) && isRed(node.left.left)){node = rightRotate(node);}//判断是否需要颜色翻转if(isRed(node.left) && isRed(node.right)){flipColors(node);}/**==========维护红黑树性质 End==========*/return node;}/*** 查找红黑树的最小值** @param* @return V* @version 2018/8/18*/public V minimum(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return minimum(root).value;}/*** 查找以node为根节点红黑树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node minimum(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.left == null){return node;}return minimum(node.left);}/*** 查找红黑树的最大值** @param* @return V* @version 2018/8/18*/public V maximize(){if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}return maximize(root).value;}/*** 查找以node为根节点红黑树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node maximize(Node node) {if(isEmpty()){throw new IllegalArgumentException("BinarySearchTree is empty !");}if(node.right == null){return node;}return minimum(node.right);}/*** 删除红黑树的最大值** @param* @return V* @version 2018/8/18*/public V removeMax(){V maximize = maximize();removeMax(root);return maximize;}/*** 删除以node为根的红黑树的最大节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMax(Node node){if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}node.right = removeMin(node.right);return node;}/*** 删除红黑树的最小值** @param* @return BinarySearchTree<E>.Node* @version 2018/8/18*/public V removeMin(){V minimum = minimum();removeMin(root);return minimum;}/*** 删除以node为根的红黑树的最小节点* 深度优先遍历，递归实现** @param node* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node removeMin(Node node){if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}node.left = removeMin(node.left);return node;}public V remove(K key) {Node node = getNode(root,key);if(node != null){root = remove(root, key);return node.value;}return null;}/*** 删除以node为根的红黑树中的指定元素* 深度优先遍历，递归实现** @param node* @param key* @return BinarySearchTree<E>.Node* @version 2018/8/18*/private Node remove(Node node, K key) {if(node == null){return null;}if(key.compareTo(node.key) < 0){node.left = remove(node.left,key);return node;}else if(key.compareTo(node.key) > 0){node.right = remove(node.right,key);return node;}else /*if(key.compareTo(node.key) == 0)*/{// 删除右子树为空的情况if(node.right == null){Node leftNode = node.left;node.left = null;size --;return leftNode;}// 删除左子树为空的情况else if(node.left == null){Node rightNode = node.right;node.right = null;size --;return rightNode;}// 删除左子树、右子树均不为空的情况else {// 1、删除后用后继节点替代该位置(后继节点即待删除节点右子树中的最小节点)// 获得后继节点Node successor = minimum(node.right);// 删除后继节点，并让待删除节点的右子树成为后继节点的右子树successor.right = removeMin(node);// 让待删除节点的左子树成为后继节点的左子树successor.left = node.left;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return successor;/**// 2、删除后用前驱节点替代该位置(前驱节点即待删除节点左子树中的最大节点)// 获得前驱节点Node predecessor = maximize(node.left);// 删除前驱节点，并让待删除节点的左子树成为前驱节点的左子树predecessor.left = removeMax(node);// 让待删除节点的右子树成为前驱节点的右子树predecessor.right = node.right;// 将待删除节点的左、右子节点置为空node.left = node.right = null;return predecessor;*/}}}public boolean contains(K key) {return getNode(root,key) != null;}public V get(K key) {Node node = getNode(root, key);return node != null ? node.value : null;}public void set(K key, V value) {Node node = getNode(root, key);if(node == null){throw new IllegalArgumentException("Set failed. key is not exists!");}node.value = value;}public int getSize() {return size;}public boolean isEmpty() {return size == 0;}/*** 根据key获取Node** @param node* @param key* @return map.LinkedListMap<K,V>.Node*/public Node getNode(Node node,K key){if(node == null){return null;}if(key.compareTo(node.key) == 0){return node;}else if(key.compareTo(node.key) < 0){return getNode(node.left,key);}else{return getNode(node.right,key);}}/*** 节点类** @version 2018/8/18*/private class Node{public K key;public V value;public Node left,right;public boolean color;public Node(K key, V value){this.key = key;this.value = value;left = null;right = null;color = RED;}}
}

RedBlackTreeMap.java

package map;/*** 利用红黑树实现映射** @version 2018/9/2*/
public class RedBlackTreeMap<K extends Comparable<K>,V> implements Map<K,V>{private RedBlackTree<K,V> redBlackTree;public RedBlackTreeMap() {redBlackTree = new RedBlackTree<>();}@Overridepublic void add(K key, V value) {redBlackTree.add(key, value);}@Overridepublic V remove(K key) {return redBlackTree.remove(key);}@Overridepublic boolean contains(K key) {return redBlackTree.contains(key);}@Overridepublic V get(K key) {return redBlackTree.get(key);}@Overridepublic void set(K key, V value) {redBlackTree.set(key, value);}@Overridepublic int getSize() {return redBlackTree.getSize();}@Overridepublic boolean isEmpty() {return redBlackTree.isEmpty();}
}

四、基于链表的Map

LinkedListMap.java

package map;/*** 利用链表实现映射** @version 2018/8/19*/
public class LinkedListMap<K,V> implements Map<K,V>{/** 虚拟头节点*/private Node dummyHead;/** 链表大小*/private int size;public LinkedListMap() {dummyHead = new Node(null,null,null);size = 0;}@Overridepublic void add(K key, V value) {Node node = getNode(key);if(node != null){throw new IllegalArgumentException("Add failed. key is exists!");}dummyHead.next = new Node(key,value,dummyHead.next);size ++;}@Overridepublic V remove(K key) {Node node = getNode(key);if(node == null){throw new IllegalArgumentException("Remove failed. key is not exists!");}Node prev = dummyHead;while (prev.next != null){if(prev.next.key.equals(key)){break;}prev = prev.next;}if(prev.next != null){Node delNode = prev.next;prev.next = delNode.next;delNode.next = null;size --;return delNode.value;}return null;}@Overridepublic boolean contains(K key) {return getNode(key) != null;}@Overridepublic V get(K key) {Node node = getNode(key);return node != null ? node.value : null;}@Overridepublic void set(K key, V value) {Node node = getNode(key);if(node == null){throw new IllegalArgumentException("Set failed. key is not exists!");}node.value = value;}@Overridepublic int getSize() {return size;}@Overridepublic boolean isEmpty() {return size == 0;}/*** 根据key获取Node** @param key* @return map.LinkedListMap<K,V>.Node*/private Node getNode(K key){Node cur = dummyHead.next;while (cur != null){if(cur.key.equals(key)){return cur;}cur = cur.next;}return null;}private class Node{private K key;private V value;private Node next;public Node(K key, V value, Node next) {this.key = key;this.value = value;this.next = next;}public Node(K key) {this.key = key;}public Node() {this(null,null,null);}@Overridepublic String toString() {return key.toString() + " : " + value.toString();}}
}

这篇关于数据结构-高层数据结构：映射/字典（Map）【有序字典：基于二分搜索树、基于平衡二叉树、基于红黑树、基于链表】【无序字典：基于哈希表】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1128846。

相关文章

Go语言中三种容器类型的数据结构详解

Go语言中三种容器类型的数据结构详解

《Go语言中三种容器类型的数据结构详解》在Go语言中,有三种主要的容器类型用于存储和操作集合数据：本文主要介绍三者的使用与区别,感兴趣的小伙伴可以跟随小编一起学习一下... 目录基本概念1. 数组（Array）2. 切片（Slice）3. 映射（Map）对比总结注意事项基本概念在 Go 语言中，有三种主要
阅读更多...
Java中基于注解的代码生成工具MapStruct映射使用详解

Java中基于注解的代码生成工具MapStruct映射使用详解

《Java中基于注解的代码生成工具MapStruct映射使用详解》MapStruct作为一个基于注解的代码生成工具,为我们提供了一种更加优雅、高效的解决方案,本文主要为大家介绍了它的具体使用,感兴趣... 目录介绍优缺点优点缺点核心注解及详细使用语法说明@Mapper@Mapping@Mappings@Co
阅读更多...
Go语言利用泛型封装常见的Map操作

Go语言利用泛型封装常见的Map操作

《Go语言利用泛型封装常见的Map操作》Go语言在1.18版本中引入了泛型,这是Go语言发展的一个重要里程碑,它极大地增强了语言的表达能力和灵活性,本文将通过泛型实现封装常见的Map操作,感... 目录什么是泛型泛型解决了什么问题Go泛型基于泛型的常见Map操作代码合集总结什么是泛型泛型是一种编程范式，允
阅读更多...
JSON字符串转成java的Map对象详细步骤

JSON字符串转成java的Map对象详细步骤

《JSON字符串转成java的Map对象详细步骤》：本文主要介绍如何将JSON字符串转换为Java对象的步骤,包括定义Element类、使用Jackson库解析JSON和添加依赖,文中通过代码介绍... 目录步骤 1: 定义 Element 类步骤 2: 使用 Jackson 库解析 jsON步骤 3: 添
阅读更多...
Java中List转Map的几种具体实现方式和特点

Java中List转Map的几种具体实现方式和特点

《Java中List转Map的几种具体实现方式和特点》：本文主要介绍几种常用的List转Map的方式,包括使用for循环遍历、Java8StreamAPI、ApacheCommonsCollect... 目录前言1、使用for循环遍历：2、Java8 Stream API：3、Apache Commons
阅读更多...
在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码

《在MyBatis的XML映射文件中＜trim＞元素所有场景下的完整使用示例代码》在MyBatis的XML映射文件中,trim元素用于动态添加SQL语句的一部分,处理前缀、后缀及多余的逗号或连接符,示... 在MyBATis的XML映射文件中，<trim>元素用于动态地添加SQL语句的一部分，例如SET或W
阅读更多...
python 字典d[k]中key不存在的解决方案

python 字典d[k]中key不存在的解决方案

《python字典d[k]中key不存在的解决方案》本文主要介绍了在Python中处理字典键不存在时获取默认值的两种方法,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,... 目录defaultdict：处理找不到的键的一个选择特殊方法__missing__有时候为了方便起见，
阅读更多...
基于Redis有序集合实现滑动窗口限流的步骤

基于Redis有序集合实现滑动窗口限流的步骤

《基于Redis有序集合实现滑动窗口限流的步骤》滑动窗口算法是一种基于时间窗口的限流算法,通过动态地滑动窗口,可以动态调整限流的速率,Redis有序集合可以用来实现滑动窗口限流,本文介绍基于Redis... 滑动窗口算法是一种基于时间窗口的限流算法，它将时间划分为若干个固定大小的窗口，每个窗口内记录了该时间
阅读更多...
C# ComboBox下拉框实现搜索方式

C# ComboBox下拉框实现搜索方式

《C#ComboBox下拉框实现搜索方式》文章介绍了如何在加载窗口时实现一个功能,并在ComboBox下拉框中添加键盘事件以实现搜索功能,由于数据不方便公开,作者表示理解并希望得到大家的指教... 目录C# ComboBox下拉框实现搜索步骤一步骤二步骤三总结C# ComboBox下拉框实现搜索步骤一这
阅读更多...
哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题  2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言 哈希表主要是适合于快速查找某个元素（O(1)） 当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。 最简单的比如数组模拟字符存储，只要开26个c
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2