数据结构-高层数据结构：集合（Set）【元素不重复】【基于二分搜索树（有序集合O(logn)）、基于平衡二叉树（有序集合O(logn)）、基于链表（无序集合O(n)）、基于哈希表（无序集合O(n)）】

爱被打了一巴掌 2023-10-04 12:30 24阅读 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]  
Set.java

package set;
    
    /**
     * 集合
     *
     * @author ronglexie
     * @version 2018/8/18
     */
    public interface Set<E> {
        
    
    	/**
    	 * 向集合中添加元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	void add(E e);
    
    	/**
    	 * 删除集合中的某个元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	void remove(E e);
    
    	/**
    	 * 查看是否包含某个元素
    	 *
    	 * @param e
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	boolean contains(E e);
    
    	/**
    	 * 获取集合的大小
    	 *
    	 * @param
    	 * @return int
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	int getSize();
    
    	/**
    	 * 判断集合是否为空
    	 *
    	 * @param
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	boolean isEmpty();
    }

## 一、基于二分搜索树实现的Set ##

BinarySearchTree.java

package set;
    
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;
    
    /**
     * 二分搜索树
     *
     * @author ronglexie
     * @version 2018/8/18
     */
    public class BinarySearchTree<E extends Comparable<E>> {
        
    
    	private Node root;
    	private int size;
    
    	public BinarySearchTree() {
        
    		root = null;
    		size = 0;
    	}
    
    	public BinarySearchTree(Node e){
        
    		root = e;
    		size ++;
    	}
    
    	public int size(){
        
    		return size;
    	}
    
    	public boolean isEmpty(){
        
    		return size == 0;
    	}
    
    	/**
    	 * 向二分搜索树中添加元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void add(E e){
        
    		root = add(root,e);
    	}
    	/**
    	 * 向node为根元素的二分搜索树中插入元素
    	 * 递归算法
    	 *
    	 * @param node
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	@Deprecated
    	private void addDeprecated(Node node,E e){
        
    		/** 递归终止条件：判断根节点、根a节点的左右节点是否为空*/
    		if(e.equals(node.e)){
        
    			return;
    		}else if(e.compareTo(node.e) < 0 && node.left == null){
        
    			node.left = new Node(e);
    			size ++;
    			return;
    		}else if(e.compareTo(node.e) > 0 && node.right == null){
        
    			node.right = new Node(e);
    			size ++;
    			return;
    		}
    
    		if(e.compareTo(node.e) < 0){
        
    			addDeprecated(node.left,e);
    		}else if(e.compareTo(node.e) > 0){
        
    			addDeprecated(node.right,e);
    		}
    	}
    
    	/**
    	 * 向node为根元素的二分搜索树中插入元素
    	 * 递归算法
    	 *
    	 * @param node
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private Node add(Node node, E e){
        
    		//递归终止条件，返回结果为null
    		if(node == null){
        
    			size ++;
    			return new Node(e);
    		}
    
    		if(e.compareTo(node.e) < 0){
        
    			node.left = add(node.left,e);
    		}else if(e.compareTo(node.e) > 0){
        
    			node.right = add(node.right,e);
    		}
    		return node;
    	}
    
    	/**
    	 * 判断二分搜索树是否包含某个元素
    	 *
    	 * @param e
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public boolean contains(E e){
        
    		return contains(root,e);
    	}
    
    	/**
    	 * 判断以node为根元素的二分搜索树是否包含某个元素
    	 *
    	 * @param node
    	 * @param e
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private boolean contains(Node node,E e){
        
    		if(node == null){
        
    			return false;
    		}
    		if(e.compareTo(node.e) == 0){
        
    			return true;
    		}else if(e.compareTo(node.e) < 0){
        
    			return contains(node.left,e);
    		}else /*if(e.compareTo(node.e) < 0)*/{
        
    			return contains(node.right,e);
    		}
    	}
    
    	/**
    	 * 前序遍历二分搜索树
    	 *
    	 * @param
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void preOrder(){
        
    		preOrder(root);
    	}
    
    	/**
    	 * 前序遍历以node为根节点的二分搜索树
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private void preOrder(Node node){
        
    		if(node == null){
        
    			return;
    		}
    		System.out.println(node.e);
    		preOrder(node.left);
    		preOrder(node.right);
    	}
    
    	/**
    	 * 前序遍历二分搜索树
    	 * 深度优先遍历，非递归实现，利用栈结构
    	 *
    	 * @param
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void preOrderNR(){
        
    		Stack<Node> stack = new Stack<>();
    		stack.push(root);
    		while (!stack.isEmpty()){
        
    			Node cur = stack.pop();
    			System.out.println(cur.e);
    			if(cur.right != null){
        
    				stack.push(cur.right);
    			}
    			if(cur.left != null){
        
    				stack.push(cur.left);
    			}
    		}
    	}
    
    	/**
    	 * 中序遍历二分搜索树
    	 *
    	 * @param
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void inOrder(){
        
    		inOrder(root);
    	}
    
    	/**
    	 * 中序遍历以node为根节点的二分搜索树
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private void inOrder(Node node){
        
    		if(node == null){
        
    			return;
    		}
    		inOrder(node.left);
    		System.out.println(node.e);
    		inOrder(node.right);
    	}
    
    	/**
    	 * 后序遍历二分搜索树
    	 *
    	 * @param
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void postOrder(){
        
    		postOrder(root);
    	}
    
    	/**
    	 * 后序遍历以node为根节点的二分搜索树
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private void postOrder(Node node){
        
    		if(node == null){
        
    			return;
    		}
    		postOrder(node.left);
    		postOrder(node.right);
    		System.out.println(node.e);
    	}
    
    	/**
    	 * 层序遍历二分搜索树
    	 * 广度优先遍历，利用队列结构
    	 *
    	 * @param
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void levelOrder(){
        
    		Queue<Node> nodeQueue = new LinkedList<>();
    		nodeQueue.add(root);
    		while (!nodeQueue.isEmpty()){
        
    			Node cur = nodeQueue.poll();
    			System.out.println(cur.e);
    			if(cur.left != null){
        
    				nodeQueue.add(cur.left);
    			}
    			if(cur.right != null){
        
    				nodeQueue.add(cur.right);
    			}
    		}
    	}
    
    	/**
    	 * 查找二分搜索树的最小值
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public E minimum(){
        
    		if(isEmpty()){
        
    			throw new IllegalArgumentException("BinarySearchTree is empty !");
    		}
    		return minimum(root).e;
    	}
    
    	/**
    	 * 查找以node为根节点二分搜索树的最小节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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 E
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public E maximize(){
        
    		if(isEmpty()){
        
    			throw new IllegalArgumentException("BinarySearchTree is empty !");
    		}
    		return maximize(root).e;
    	}
    
    	/**
    	 * 查找以node为根节点二分搜索树的最大节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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 BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public E removeMax(){
        
    		E maximize = maximize();
    		removeMax(root);
    		return maximize;
    	}
    
    	/**
    	 * 删除以node为根的二分搜索树的最大节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public E removeMin(){
        
    		E minimum = minimum();
    		removeMin(root);
    		return minimum;
    	}
    
    	/**
    	 * 删除以node为根的二分搜索树的最小节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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;
    	}
    
    	/**
    	 * 删除二分搜索树中的指定元素
    	 *
    	 * @param e
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void remove(E e){
        
    		root = remove(root,e);
    	}
    
    	/**
    	 * 删除以node为根的二分搜索树中的指定元素
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @param e
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private Node remove(Node node, E e) {
        
    		if(node == null){
        
    			return null;
    		}
    		if(e.compareTo(node.e) < 0){
        
    			node.left = remove(node.left,e);
    			return node;
    		}else if(e.compareTo(node.e) > 0){
        
    			node.right = remove(node.right,e);
    			return node;
    		}else /*if(e.compareTo(node.e) == 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 String toString() {
        
    		StringBuilder result = new StringBuilder();
    		generateBSTString(root,0,result);
    		return result.toString();
    	}
    
    	/**
    	 * 生成二分搜索树的字符
    	 *
    	 * @param node
    	 * @param depth
    	 * @param result
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private void generateBSTString(Node node, int depth, StringBuilder result) {
        
    		if (node == null) {
        
    			result.append(generateBSTString(depth)+"null\n");
    			return;
    		}
    		result.append(generateBSTString(depth)+node.e+"\n");
    		generateBSTString(node.left,depth+1,result);
    		generateBSTString(node.right,depth+1,result);
    	}
    
    	/**
    	 * 生成表示深度的字符
    	 *
    	 * @param depth
    	 * @return java.lang.String
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private String generateBSTString(int depth) {
        
    		StringBuilder result = new StringBuilder();
    		for (int i = 0; i < depth; i++) {
        
    			result.append("--");
    		}
    		return result.toString();
    	}
    
    	/**
    	 * 节点类
    	 *
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	private class Node{
        
    		public E e;
    		public Node left,right;
    
    		public Node(E e){
        
    			this.e = e;
    			left = null;
    			right = null;
    		}
    	}
    }

BinarySearchTreeSet.java

package set;
    
    /**
     * 利用二分搜索树实现集合
     * 不包含重复元素
     *
     * @author ronglexie
     * @version 2018/8/18
     */
    public class BinarySearchTreeSet<E extends Comparable<E>> implements Set<E> {
        
    
    	private BinarySearchTree<E> binarySearchTree;
    
    	public BinarySearchTreeSet() {
        
    		binarySearchTree = new BinarySearchTree<>();
    	}
    
    	@Override
    	public void add(E e) {
        
    		binarySearchTree.add(e);
    	}
    
    	@Override
    	public void remove(E e) {
        
    		binarySearchTree.remove(e);
    	}
    
    	@Override
    	public boolean contains(E e) {
        
    		return binarySearchTree.contains(e);
    	}
    
    	@Override
    	public int getSize() {
        
    		return binarySearchTree.size();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		return binarySearchTree.isEmpty();
    	}
    }

## 二、基于平衡二叉树(AVL)实现的Set ##

AVLTree.java

package set;
    
    import java.util.ArrayList;
    
    /**
     * AVL平衡二叉树
     *
     * @author ronglexie
     * @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
    	 * @author ronglexie
    	 * @version 2018/9/1
    	 */
    	private int getHeight(Node node){
        
    		if(node == null){
        
    			return 0;
    		}
    		return node.height;
    	}
    
    	/**
    	 * 获取某个节点的平衡因子
    	 *
    	 * @param node
    	 * @return int
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/9/1
    	 */
    	private boolean isBalanced(){
        
    		return isBalanced(root);
    	}
    
    	/**
    	 * 递归查看以node为根节点的AVL平衡二叉树是否是平衡二叉树
    	 *
    	 * @param node
    	 * @return boolean
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public V removeMax(){
        
    		V maximize = maximize();
    		removeMax(root);
    		return maximize;
    	}
    
    	/**
    	 * 删除以node为根的AVL平衡二叉树的最大节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public V removeMin(){
        
    		V minimum = minimum();
    		removeMin(root);
    		return minimum;
    	}
    
    	/**
    	 * 删除以node为根的AVL平衡二叉树的最小节点
    	 * 深度优先遍历，递归实现
    	 *
    	 * @param node
    	 * @return BinarySearchTree<E>.Node
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @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
    	 * @author ronglexie
    	 * @version 2018/8/19
    	 */
    	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);
    		}
    	}
    
    	/**
    	 * 节点类
    	 *
    	 * @author ronglexie
    	 * @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");
    			}
    		}
    	}
    }

AVLTreeSet.java

package set;
    
    /**
     * 利用AVL平衡二叉树实现集合
     * 不包含重复元素
     *
     * @author ronglexie
     * @version 2018/9/1
     */
    public class AVLTreeSet<E extends Comparable<E>> implements Set<E> {
        
    
    	AVLTree<E,Object> avlTree;
    
    	public AVLTreeSet() {
        
    		avlTree = new AVLTree<>();
    	}
    
    	@Override
    	public void add(E e) {
        
    		avlTree.add(e, null);
    	}
    
    	@Override
    	public void remove(E e) {
        
    		avlTree.remove(e);
    	}
    
    	@Override
    	public boolean contains(E e) {
        
    		return avlTree.contains(e);
    	}
    
    	@Override
    	public int getSize() {
        
    		return avlTree.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		return avlTree.isEmpty();
    	}
    }

## 三、基于链表实现的Set ##

LinkedList.java

package set;
    
    /**
     * 链表
     * 包含头指针、虚拟节点
     *
     * @author ronglexie
     * @version 2018/8/11
     */
    public class LinkedList<E> {
        
    
    	/** 虚拟头节点*/
    	private Node dummyHead;
    	/** 链表大小*/
    	private int size;
    
    	public LinkedList() {
        
    		dummyHead = new Node(null,null);
    		size = 0;
    	}
    
    	public int getSize(){
        
    		return size;
    	}
    
    	public boolean isEmpty(){
        
    		return size == 0;
    	}
    
    	/**
    	 * 向链表指定位置添加元素
    	 *
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public void add(int index, E e){
        
    		if(index < 0 || index > size){
        
    			throw new IllegalArgumentException("Add faild. Illegal index.");
    		}
    		Node prev = dummyHead;
    		for (int i = 0; i < index; i++) {
        
    			prev = prev.next;
    		}
    
    		prev.next = new Node(e,prev.next);
    
    		size ++;
    	}
    
    	/**
    	 * 向链表头添加元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public void addFirst(E e){
        
    		add(0,e);
    	}
    
    	/**
    	 * 向链表尾部添加元素
    	 *
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public void addLast(E e){
        
    		add(size,e);
    	}
    
    	/**
    	 * 获取指定位置元素
    	 *
    	 * @param index
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E get(int index){
        
    		if(index < 0 || index > size){
        
    			throw new IllegalArgumentException("Get faild. Illegal index.");
    		}
    		Node cur = dummyHead.next;
    		for (int i = 0; i < index; i++) {
        
    			cur = cur.next;
    		}
    		return cur.e;
    	}
    
    	/**
    	 * 获取链表头部的元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E getFirst(){
        
    		return get(0);
    	}
    
    	/**
    	 * 获取链表尾部的元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E getLast(){
        
    		return get(size);
    	}
    
    	/**
    	 * 修改指定位置的元素
    	 *
    	 * @param index
    	 * @param e
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public void set(int index, E e){
        
    		if(index < 0 || index > size){
        
    			throw new IllegalArgumentException("Set failed. Illegal index.");
    		}
    		Node cur = dummyHead.next;
    		for (int i = 0; i < index; i++) {
        
    			cur = cur.next;
    		}
    		cur.e = e;
    	}
    
    	/**
    	 * 判断链表是否包含某个元素
    	 *
    	 * @param e
    	 * @return boolean
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public boolean contains(E e){
        
    		Node cur = dummyHead.next;
    		while (cur != null){
        
    			if (cur.e.equals(e)){
        
    				return true;
    			}
    			cur = cur.next;
    		}
    		return false;
    	}
    
    	/**
    	 * 删除指定位置的元素
    	 *
    	 * @param index
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E remove(int index){
        
    		if(index < 0 || index > size){
        
    			throw new IllegalArgumentException("Delete failed. Illegal index.");
    		}
    		Node prev = dummyHead;
    		for (int i = 0; i < index; i++) {
        
    			prev = prev.next;
    		}
    		Node delNode = prev.next;
    		prev.next = delNode.next;
    		delNode.next = null;
    		size --;
    		return delNode.e;
    	}
    
    	/**
    	 * 删除指定元素
    	 *
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void remove(E e){
        
    		if(!contains(e)){
        
    			throw new IllegalArgumentException("Delete failed. e is not exists.");
    		}
    		Node prev = dummyHead;
    		while (prev.next != null){
        
    			if(prev.next.e.equals(e)){
        
    				break;
    			}
    			prev = prev.next;
    		}
    
    		if(prev.next != null){
        
    			Node delNode = prev.next;
    			prev.next = delNode.next;
    			delNode.next = null;
    			size --;
    		}
    	}
    
    	/**
    	 * 删除所有的指定元素
    	 *
    	 * @return void
    	 * @author ronglexie
    	 * @version 2018/8/18
    	 */
    	public void removeAll(E e){
        
    		if(!contains(e)){
        
    			throw new IllegalArgumentException("Delete failed. e is not exists.");
    		}
    		Node prev = dummyHead;
    		while (prev.next != null){
        
    			if(prev.next.e.equals(e)){
        
    				Node delNode = prev.next;
    				prev.next = delNode.next;
    				delNode.next = null;
    				size --;
    				continue;
    			}
    			prev = prev.next;
    		}
    	}
    
    	/**
    	 * 删除链表头部的元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E removeFirst(){
        
    		return remove(0);
    	}
    
    	/**
    	 * 删除链表尾部的元素
    	 *
    	 * @param
    	 * @return E
    	 * @author ronglexie
    	 * @version 2018/8/12
    	 */
    	public E removeLast(){
        
    		return remove(size - 1);
    	}
    
    	@Override
    	public String toString() {
        
    		StringBuilder result = new StringBuilder();
    		result.append(String.format("LinkedList: size: %d\n",size));
    		result.append("head ");
    		Node cur = dummyHead.next;
    		while (cur != null){
        
    			result.append(cur+ "->");
    			cur = cur.next;
    		}
    		result.append("NULL");
    		return result.toString();
    	}
    
    	private class Node{
        
    
    		private E e;
    		private Node next;
    
    		public Node(E e, Node next) {
        
    			this.e = e;
    			this.next = next;
    		}
    
    		public Node(E e) {
        
    			this.e = e;
    		}
    
    		public Node() {
        
    			this(null,null);
    		}
    
    		@Override
    		public String toString() {
        
    			return e.toString();
    		}
    	}
    }

LinkedListSet.java

package set;
    
    /**
     * 利用链表实现集合
     *
     * @author ronglexie
     * @version 2018/8/18
     */
    public class LinkedListSet<E> implements Set<E> {
        
    
    	private LinkedList linkedList;
    
    	public LinkedListSet() {
        
    		linkedList = new LinkedList();
    	}
    
    	@Override
    	public void add(E e) {
        
    		if(!linkedList.contains(e)){
        
    			linkedList.addFirst(e);
    		}
    	}
    
    	@Override
    	public void remove(E e) {
        
    		linkedList.remove(e);
    	}
    
    	@Override
    	public boolean contains(E e) {
        
    		return linkedList.contains(e);
    	}
    
    	@Override
    	public int getSize() {
        
    		return linkedList.getSize();
    	}
    
    	@Override
    	public boolean isEmpty() {
        
    		return linkedList.isEmpty();
    	}
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20210504120711994.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/20210504122625177.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/20210504122229787.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTMyNTA4NjE=,size_16,color_FFFFFF,t_70#pic_center