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

本是古典何须时尚 2023-10-04 12:30 22阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]

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;
    	}
    
    	@Override
    	public 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){
        
    		//递归终止条件，返回结果为null
    		if(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;
    	}
    
    	@Override
    	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;
    				 */
    			}
    		}
    	}
    
    	@Override
    	public boolean contains(K key) {
        
    		return getNode(root,key) != null;
    	}
    
    	@Override
    	public V get(K key) {
        
    		Node node = getNode(root, key);
    		return node != null ? node.value : null;
    	}
    
    	@Override
    	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;
    	}
    
    	@Override
    	public int getSize() {
        
    		return size;
    	}
    
    	@Override
    	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 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;
    
    		//更新height
    		y.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;
    
    		//更新height
    		y.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){
        
    		//递归终止条件，返回结果为null
    		if(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 ==========*/
    		//更新Height
    		node.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;
    		}
    
    		//更新Height
    		resultNode.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();
    	}
    
    	@Override
    	public void add(K key, V value) {
        
    		avlTree.add(key, value);
    	}
    
    	@Override
    	public V remove(K key) {
        
    		return avlTree.remove(key);
    	}
    
    	@Override
    	public boolean contains(K key) {
        
    		return avlTree.contains(key);
    	}
    
    	@Override
    	public V get(K key) {
        
    		return avlTree.get(key);
    	}
    
    	@Override
    	public void set(K key, V value) {
        
    		avlTree.set(key, value);
    	}
    
    	@Override
    	public int getSize() {
        
    		return avlTree.getSize();
    	}
    
    	@Override
    	public 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   T2
    	private 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  T2
    	private 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){
        
    		//递归终止条件，返回结果为null
    		if(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<>();
    	}
    
    	@Override
    	public void add(K key, V value) {
        
    		redBlackTree.add(key, value);
    	}
    
    	@Override
    	public V remove(K key) {
        
    		return redBlackTree.remove(key);
    	}
    
    	@Override
    	public boolean contains(K key) {
        
    		return redBlackTree.contains(key);
    	}
    
    	@Override
    	public V get(K key) {
        
    		return redBlackTree.get(key);
    	}
    
    	@Override
    	public void set(K key, V value) {
        
    		redBlackTree.set(key, value);
    	}
    
    	@Override
    	public int getSize() {
        
    		return redBlackTree.getSize();
    	}
    
    	@Override
    	public 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;
    	}
    
    
    	@Override
    	public 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 ++;
    	}
    
    	@Override
    	public 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;
    	}
    
    	@Override
    	public boolean contains(K key) {
        
    		return getNode(key) != null;
    	}
    
    	@Override
    	public V get(K key) {
        
    		Node node = getNode(key);
    		return node != null ? node.value : null;
    	}
    
    	@Override
    	public 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;
    	}
    
    	@Override
    	public int getSize() {
        
    		return size;
    	}
    
    	@Override
    	public 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);
    		}
    
    		@Override
    		public String toString() {
        
    			return key.toString() + " : " + value.toString();
    		}
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210504145613896.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20210504150625171.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 2]: https://img-blog.csdnimg.cn/20210504150736867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center 3]: https://img-blog.csdnimg.cn/20210504151039116.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center