数据结构(七)-树

参考文献

• 二叉树理论基础篇

理论

二叉树的高度

• 二叉树节点的高度:指从该节点到叶子节点的最长简单路径边的条数后者节点数（取决于高度从0开始还是从1开始),而根节点的高度就是二叉树的最大深度

       1
     /   \
    2     3
   / \   / \
  4   5 6   7
 /
8

二叉树的深度

• 二叉树节点的深度:指从根节点到该节点的最长简单路径边的条数或者节点数（取决于深度从0开始还是从1开始）

       1
     /   \
    2     3
   / \   / \
  4   5 6   7
 /
8

满二叉树

• 满二叉树是一种特殊的二叉树,除了叶子节点,每个节点都有左右两个子节点,并且所有叶子节点都在同一层上.也就是说,满二叉树的深度为h,它的节点数为$2^{ h - 1}$.

完全二叉树

• 完全二叉树是一种特殊的二叉树,除了最后一层之外,其他层的节点数都是满的,并且最后一层的节点都集中在左侧.也就是说,如果最后一层的节点数为m,那么前面的所有层都是满的,并且节点数为$2^{h-1}$,总共的节点数为$2^{h-1} + m$.
• 需要注意的是,满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树.

二叉搜索树

• 二叉搜索树(Binary Search Tree,BST)是一种特殊的二叉树,它的每个节点都包含一个键值,且满足以下性质:
  1. 左子树中所有节点的键值都小于当前节点的键值；
  2. 右子树中所有节点的键值都大于当前节点的键值；
  3. 左右子树都是二叉搜索树(递归定义)
• 由于满足以上性质,二叉搜索树支持快速插入、删除和查找操作.对于任意节点,它的左子树中所有节点的键值都小于该节点的键值,右子树中所有节点的键值都大于该节点的键值,这样就可以用二分查找的方式快速定位某个节点.
• 在二叉搜索树中,插入和删除操作需要保持树的有序性质,即插入节点时需要找到正确的位置,删除节点时需要保持左右子树仍然是二叉搜索树,并且保持树的平衡性.
• 当二叉搜索树的左右子树分布不均时,可能会导致树的高度很大,从而影响查找效率.为了解决这个问题,可以使用平衡二叉搜索树,例如AVL树、红黑树等,来保持树的平衡性和性能.

平衡二叉搜索树

• 平衡二叉搜索树(Balanced Binary Search Tree)是指一类特殊的二叉搜索树,它能够自动调整树的形态,使得树的高度保持在一个较小的范围内,进而保证查找、插入、删除等操作的效率.常见的平衡二叉搜索树包括 AVL 树、红黑树、B 树等.

• 在平衡二叉搜索树中,每个节点都有一个平衡因子,通常是左子树的高度减去右子树的高度.如果平衡因子的绝对值超过了1,就需要对该节点的子树进行旋转操作,以调整树的形态,使其更加平衡.

• 旋转操作分为左旋和右旋两种,左旋是指将节点的右子树提升到该节点的位置,同时该节点成为左子节点的右子节点,右旋是指将节点的左子树提升到该节点的位置,同时该节点成为右子节点的左子节点.通过旋转操作,可以使得树的高度保持在一个较小的范围内,从而保证了查找、插入、删除等操作的性能.

• 平衡二叉搜索树在实际应用中有广泛的应用,例如数据库索引、编译器中的符号表、路由表等.常见的平衡二叉搜索树有 AVL 树、红黑树、B 树等,每种平衡二叉搜索树都有其特点和适用场景.

• 在 Java 集合类中,有两种类实现了平衡二叉树.

  • TreeMap 类:TreeMap 类实现了SortedMap接口,底层使用红黑树(Red-Black Tree)来实现,可以保证元素按照键的自然顺序进行排序.TreeMap 中的每个节点都包含了一个键值对,其中键是唯一的,值可以重复.

  • TreeSet 类:TreeSet 类实现了SortedSet接口,底层使用红黑树(Red-Black Tree)来实现,可以保证元素按照自然顺序进行排序.TreeSet 中的元素都是唯一的,不允许重复.

二叉树的存储方式

• 链式存储:每个节点保存指向其左子树和右子树的指针(或引用).这种存储方式适合于动态变化的二叉树,但是需要额外的空间来存储指针.
• 数组存储:使用数组来存储二叉树的节点,按照某种顺序将节点存储在数组中,并使用数组下标来表示节点的位置.这种存储方式可以节省空间,但是不适合动态变化的二叉树.

二叉树的遍历

• 二叉树主要有两种遍历方式:

  • 深度优先遍历(Depth-First Search,DFS):先往深走,遇到叶子节点再往回走.

    • 前序遍历(递归法,迭代法)

      • 中左右

    • 中序遍历(递归法,迭代法)

      • 左中右

    • 后序遍历(递归法,迭代法)

      • 左右中

  • 广度优先遍历Breadth-First Search,BST:一层一层的去遍历.

    • 层次遍历(迭代法)

      public List<List<Integer>> levelOrder(TreeNode root) {
              List<List<Integer>> result = new ArrayList<>();
              if (root == null) {
                  return result;
              }
              Queue<TreeNode> que = new LinkedList<TreeNode>();
              que.offer(root);
      
              while (!que.isEmpty()) {
                  List<Integer> itemList = new ArrayList<Integer>();
                  int len = que.size();
                  while (len > 0) {
                      TreeNode tmpNode = que.poll();
                      itemList.add(tmpNode.val);
      
                      if (tmpNode.left != null) {
                          que.offer(tmpNode.left);
                      }
                      if (tmpNode.right != null) {
                          que.offer(tmpNode.right);
                      }
                      len--;
                  }
                  result.add(itemList);
              }
              return result;
      }

  递归算法的三个要素.每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法！

  1. 确定递归函数的参数和返回值: 确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数, 并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型.
  2. 确定终止条件: 写完了递归算法, 运行的时候,经常会遇到栈溢出的错误,就是没写终止条件或者终止条件写的不对,操作系统也是用一个栈的结构来保存每一层递归的信息,如果递归没有终止,操作系统的内存栈必然就会溢出.
  3. 确定单层递归的逻辑: 确定每一层递归需要处理的信息.在这里也就会重复调用自己来实现递归的过程.

各种树的实现

二分搜索树(BST)

• 二分搜索树: Binary Search Tree

package com.holelin.tree;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * ClassName: BST
 * 二分搜索树: Binary Search Tree
 * 注: 二分搜索树存储的元素必须有可比较性;
 * 注: 本树不包含重复元素
 * -- 左子树小于节点
 * -- 右子树大于节点
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/4
 */

public class BST<E extends Comparable<E>> {
	/**
	 * 二分搜索树根节点
	 */
	private Node root;
	/**
	 * 树中元素的个数
	 */
	private int size;

	public BST() {
		root = null;
		size = 0;
	}

	/**
	 * 获取二分搜索树中元素的个数
	 *
	 * @return 二分搜索树中元素的个数
	 */
	public int size() {
		return size;
	}

	/**
	 * 判断二分搜索树是否为空
	 *
	 * @return 为空返回true;反之返回false;
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	/**
	 * 向二分搜索树中添加新的元素e
	 *
	 * @param e 新添加的元素
	 */
	public void add(E e) {
		root = add(root, e);
	}

	/**
	 * 向以node为根的二分搜索树中插入元素E (使用递归)
	 *
	 * @param node 以node为根
	 * @param e    插入的元素
	 */
	private Node add(Node node, E e) {
		if (node == null) {
			size++;
			return new Node(e);
		}
		if (e.compareTo(node.data) < 0) {
			node.left = add(node.left, e);
		} else if (e.compareTo(node.data) > 0) {
			node.right = add(node.right, e);
		}
		return node;
	}

	/**
	 * 查询二分搜索树是否包含元素e
	 *
	 * @param e 查询元素e
	 * @return 存在返回true;反之返回false
	 */
	public boolean contains(E e) {
		return contains(root, e);
	}

	/**
	 * 看以node为根的二分搜索树是否包含元素e(递归算法)
	 *
	 * @param node 以node为根
	 * @param e    查询元素e
	 * @return 存在返回true;反之返回false
	 */
	private boolean contains(Node node, E e) {
		if (node == null) {
			return false;
		}
		if (e.equals(node.data)) {
			return true;
		} else if (e.compareTo(node.data) < 0) {
			return contains(node.left, e);
		} else {
			return contains(node.right, e);
		}
	}

	public void preOrder() {
		preOrder(root);
	}

	/**
	 * 二分搜索树的前序遍历以node为根
	 *
	 * @param node node为根
	 */
	private void preOrder(Node node) {
		if (node == null) {
			return;
		}
		System.out.print(node.data + " ");
		preOrder(node.left);
		preOrder(node.right);
	}

	/**
	 * 非递归的前序遍历
	 */
	public void preOrderNR() {
		Stack<Node> stack = new Stack<>();
		stack.push(root);
		while (!stack.isEmpty()) {
			Node cur = stack.pop();
			System.out.print(cur.data + " ");
			if (cur.right != null) {
				stack.push(cur.right);
			}
			if (cur.left != null) {
				stack.push(cur.left);
			}
		}
	}

	/**
	 * 中序遍历(顺序是有序的)
	 */
	public void inOrder() {
		inOrder(root);
	}

	/**
	 * 以node为根,中序遍历
	 *
	 * @param node 以node为根
	 */
	private void inOrder(Node node) {
		if (node == null) {
			return;
		}
		inOrder(node.left);
		System.out.print(node.data + " ");
		inOrder(node.right);
	}

	/**
	 * 后序遍历
	 */
	public void postOrder() {
		postOrder(root);
	}

	private void postOrder(Node node) {
		if (node == null) {
			return;
		}
		postOrder(node.left);
		postOrder(node.right);
		System.out.print(node.data + " ");

	}

	/**
	 * 层次遍历
	 */
	public void levelOrder() {
		Queue<Node> q = new LinkedList<>();
		((LinkedList<Node>) q).add(root);
		while (!q.isEmpty()) {
			Node cur = q.remove();
			System.out.print(cur.data + " ");
			if (cur.left != null) {
				q.add(cur.left);
			}
			if (cur.right != null) {
				q.add(cur.right);
			}
		}

	}

	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		generateBSTString(root, 0, res);
		return res.toString();
	}

	/**
	 * 生成以node为根节点,深度为depth的描述二叉树的字符串
	 *
	 * @param node  以node为根节点
	 * @param depth 深度为depth
	 * @param res   接收字符串
	 */
	private void generateBSTString(Node node, int depth, StringBuilder res) {
		if (node == null) {
			res.append(generateDepthString(depth)).append("NULL\n");
			return;
		}
		res.append(generateDepthString(depth)).append(node.data).append("\n");
		generateBSTString(node.left, depth + 1, res);
		generateBSTString(node.right, depth + 1, res);


	}

	private String generateDepthString(int depth) {
		StringBuilder res = new StringBuilder();
		for (int i = 0; i < depth; i++) {
			res.append("--");

		}
		return res.toString();
	}

	/**
	 * 寻找二分搜索树的最小元素
	 *
	 * @return 二分搜索树的最小元素
	 */
	public E minimum() {
		if (size == 0) {
			throw new IllegalArgumentException("BST is empty");
		}
		return minimum(root).data;
	}

	/**
	 * 返回以node为根的二分搜索树的最小值所在的结点
	 *
	 * @param node 以node为根的二分搜索树
	 * @return 以node为根的二分搜索树的最小值所在的结点
	 */
	private Node minimum(Node node) {
		if (node.left == null) {
			return node;
		}
		return minimum(node.left);
	}

	/**
	 * 寻找二分搜索树的最大元素
	 *
	 * @return 二分搜索树的最大元素
	 */
	public E maximum() {
		if (size == 0) {
			throw new IllegalArgumentException("BST is empty");
		}
		return maximum(root).data;
	}

	/**
	 * 返回以node为根的二分搜索树的最小值所在的结点
	 *
	 * @param node 以node为根的二分搜索树
	 * @return 以node为根的二分搜索树的最小值所在的结点
	 */
	private Node maximum(Node node) {
		if (node.right == null) {
			return node;
		}
		return maximum(node.right);
	}

	/**
	 * 从二分搜索树中删除最小值所在的节点,返回最小值
	 *
	 * @return 返回最小值
	 */
	public E removeMin() {
		E ret = minimum();
		root = removeMin(root);
		return ret;
	}

	/**
	 * 删除掉以node为根的二分搜索树中的最小节点
	 * 返回删除节点后的新的二分搜索树的根
	 *
	 * @param node 以node为根的二分搜索树
	 * @return 返回删除节点后的新的二分搜索树的根
	 */
	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;
	}

	/**
	 * 从二分搜索树中删除最大值所在的节点,返回最大值
	 *
	 * @return 返回最大值
	 */
	public E removeMax() {
		E ret = maximum();
		root = removeMax(root);
		return ret;
	}

	/**
	 * 删除掉以node为根的二分搜索树中的最大节点
	 * 返回删除节点后的新的二分搜索树的根
	 *
	 * @param node 以node为根的二分搜索树
	 * @return 返回删除节点后的新的二分搜索树的根
	 */
	private Node removeMax(Node node) {
		if (node.right == null) {
			Node leftNode = node.left;
			node.left = null;
			size--;
			return leftNode;
		}
		node.right = removeMax(node.right);
		return node;
	}

	public void remove(E e) {
		root = remove(root, e);
	}

	private Node remove(Node node, E e) {
		if (node == null) {
			return null;
		}
		if (e.compareTo(node.data) < 0) {
			// 到node左子树寻找
			node.left = remove(node.left, e);
			return node;
		} else if (e.compareTo(node.data) > 0) {
			node.right = remove(node.right, e);
			return node;
		} else {
			// 待删除节点左子树为空的情况
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				size--;
				return rightNode;
			}
			// 待删除节点右子树为空的情况
			if (node.right == null) {
				Node leftNode = node.left;
				node.left = null;
				size--;
				return leftNode;
			}
			// 带删除节点左右子树均不为空的情况
			// 找到比带删除节点大的最小的节点,即待删除节点右子树的最小节点
			// 用这个节点顶替待删除节点的位置
			Node successor = minimum(node.right);
			successor.right = removeMin(node.right);
			successor.left = node.left;
			node.left = node.right = null;
			return successor;
		}
	}


	private class Node {
		/**
		 * 数据域
		 */
		public E data;
		/**
		 * 左子树地址域
		 */
		public Node left;
		/**
		 * 右子树地址域
		 */
		public Node right;

		public Node(E data) {
			this.data = data;
			this.left = null;
			this.right = null;
		}
	}

}

测试用例

package com.holelin.tree;

import java.util.ArrayList;
import java.util.Random;

/**
 * ClassName: BSTTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/4
 */

public class BSTTest {
	public static void main(String[] args) {
		BST<Integer> bst = new BST<>();
		int[] nums = {5, 3, 6, 8, 4, 2};
		for (int num : nums) {
			bst.add(num);
		}
		bst.preOrder();
		System.out.println();
		bst.preOrderNR();
		System.out.println();
		System.out.println(bst);
		bst.inOrder();
		System.out.println();
		bst.postOrder();
		System.out.println();
		bst.levelOrder();

		BST<Integer> bst1 = new BST<>();
		int n = 10000;
		Random random = new Random();
		for (int i = 0; i < n; i++) {
			bst1.add(random.nextInt(10000));
		}
		ArrayList<Integer> list = new ArrayList<>();
		while (!bst1.isEmpty()) {
			list.add(bst1.removeMin());
		}
		System.out.println();
		System.out.println(list);
		for (int i = 1; i < list.size(); i++) {
			if (list.get(i - 1) > list.get(i)) {
				throw new IllegalArgumentException("Error");
			}
		}
		System.out.println("removeMin is completed");
		for (int i = 0; i < n; i++) {
			bst1.add(random.nextInt(10000));
		}
		ArrayList<Integer> list2 = new ArrayList<>();
		while (!bst1.isEmpty()) {
			list2.add(bst1.removeMax());
		}
		System.out.println();
		System.out.println(list2);
		for (int i = 1; i < list2.size(); i++) {
			if (list2.get(i - 1) < list2.get(i)) {
				throw new IllegalArgumentException("Error");
			}
		}
		System.out.println("removeMax is completed");

	}
}

平衡二叉树(AVL树)

package com.holelin.tree;

import java.util.ArrayList;

/**
 * ClassName: AVLMap
 * AVL树(平衡二叉树)
 * -- 满足二分搜索树条件
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/17
 */

public class AVLTree<K extends Comparable<K>, V> {
	private Node root;
	private int size;

	public AVLTree() {
		root = null;
		size = 0;
	}

	/**
	 * 判断该二叉树是否是一颗平衡二叉树
	 *
	 * @return 是返回true;反之返回false;
	 */
	public boolean isBalanced() {
		return isBalanced(root);
	}

	/**
	 * 判断以node为根的二叉树是否是一颗平衡二叉树
	 *
	 * @param node 以node为根的二叉树
	 * @return 是返回true;反之返回false;
	 */
	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);
	}

	/**
	 * 判断该二叉树是否是一颗二分搜索树
	 * -- 二分搜索树的前序遍历得到的序列是由低到高的升序序列
	 *
	 * @return 是返回true;不是返回false;
	 */
	public boolean isBST() {
		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;
	}

	/**
	 * 对以node为根节点的二叉树进行前序遍历
	 *
	 * @param node 以node为根节点的二叉树
	 * @param keys 存放遍历的序列
	 */
	private void inOrder(Node node, ArrayList<K> keys) {
		if (node == null) {
			return;
		}
		inOrder(node.left, keys);
		keys.add(node.key);
		inOrder(node.right, keys);
	}

	/**
	 * 获取node的平衡因子
	 *
	 * @param node node节点
	 * @return node的平衡因子
	 */
	private int getBalanceFactor(Node node) {
		if (node == null) {
			return 0;
		}
		return getHeight(node.left) - getHeight(node.right);
	}

	/**
	 * 获得node节点的高度
	 *
	 * @param node 节点node
	 * @return node节点的高度
	 */
	private int getHeight(Node node) {
		if (node == null) {
			return 0;
		}
		return node.height;
	}

	public void add(K key, V value) {
		root = add(root, key, value);
	}

	private Node add(Node node, K key, V value) {
		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;
		}
		// 对当前的node的height进行更新
		node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
		// 计算平衡因子
		int balanceFactor = getBalanceFactor(node);
		// 平衡维护
		// 若平衡因子大于1(原因为在它的左子树的左侧添加了一个元素)
		// 该树向左偏移,getBalanceFactor(node.left) >= 0 -- 表示左子树的高度大于右子树的高度
		// LL
		if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
			// 右旋转
			return rightRotate(node);
		}
		// 该树向右偏移,getBalanceFactor(node.right) <= 0 -- 表示左子树的高度小于右子树的高度
		// RR
		if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
			return leftRotate(node);
		}
		// LR
		if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
			// 对当前节点的左孩子进行左旋转 == >LL
			node.left = leftRotate(node.left);
			return rightRotate(node);
		}
		// RL
		if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
			// 对当前节点的右孩子进行右旋转 == > RR
			node.right = rightRotate(node.right);
			return leftRotate(node);
		}
		return node;
	}

	/**
	 * 对节点y进行向右旋转操作,返回旋转后新的根节点x
	 * ----------y                          x
	 * ---------/ \                        /  \
	 * -------x   T4   向右旋转(y)         z     y
	 * ------/ \      -------------->>   / \   / \
	 * -----z   T3                     T1  T2 T3 T4
	 * ----/ \
	 * --T1   T2
	 *
	 * @param y 对y节点操作
	 * @return 右旋转后的新的节点x
	 */
	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 对y节点操作
	 * @return 左旋转后的新的节点x
	 */
	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;
	}

	private Node getNode(Node node, K key) {
		if (node == null) {
			return null;
		}
		if (node.key.compareTo(key) == 0) {
			return node;
		} else if (node.key.compareTo(key) < 0) {
			return getNode(node.left, key);
		} else {
			return getNode(node.right, key);
		}
	}

	public V remove(K key) {
		Node node = getNode(root, key);
		if (node != null) {
			root = remove(root, key);
			return root.value;
		}
		return null;
	}


	private Node remove(Node node, K key) {
		if (node == null) {
			return null;
		}
		Node retNode;
		if (key.compareTo(node.key) < 0) {
			// 到node左子树寻找
			node.left = remove(node.left, key);
			retNode = node;
		} else if (key.compareTo(node.key) > 0) {
			node.right = remove(node.right, key);
			retNode = node;
		} else {
			// 待删除节点左子树为空的情况
			if (node.left == null) {
				Node rightNode = node.right;
				node.right = null;
				size--;
				retNode = rightNode;
			} else if (node.right == null) {
				// 待删除节点右子树为空的情况
				Node leftNode = node.left;
				node.left = null;
				size--;
				retNode = leftNode;
			} else {
				// 待删除节点左右子树均不为空的情况
				// 找到比带删除节点大的最小的节点,即待删除节点右子树的最小节点
				// 用这个节点顶替待删除节点的位置
				Node successor = minimum(node.right);
				successor.right = remove(node.right, successor.key);
				successor.left = node.left;
				node.left = node.right = null;
				retNode = successor;
			}
		}
		if (retNode == null) {
			return null;
		}
		// 对当前的node的height进行更新
		retNode.height = 1 + Math.max(getHeight(retNode.left), getHeight(retNode.right));
		// 计算平衡因子
		int balanceFactor = getBalanceFactor(retNode);
		// 平衡维护
		// 若平衡因子大于1(原因为在它的左子树的左侧添加了一个元素)
		// 该树向左偏移,getBalanceFactor(node.left) >= 0 -- 表示左子树的高度大于右子树的高度
		// LL
		if (balanceFactor > 1 && getBalanceFactor(retNode.left) >= 0) {
			// 右旋转
			return rightRotate(retNode);
		}
		// 该树向右偏移,getBalanceFactor(node.right) <= 0 -- 表示左子树的高度小于右子树的高度
		// RR
		if (balanceFactor < -1 && getBalanceFactor(retNode.right) <= 0) {
			return leftRotate(retNode);
		}
		// LR
		if (balanceFactor > 1 && getBalanceFactor(retNode.left) < 0) {
			// 对当前节点的左孩子进行左旋转 == >LL
			retNode.left = leftRotate(retNode.left);
			return rightRotate(retNode);
		}
		// RL
		if (balanceFactor < -1 && getBalanceFactor(retNode.right) > 0) {
			// 对当前节点的右孩子进行右旋转 == > RR
			retNode.right = rightRotate(retNode.right);
			return leftRotate(retNode);
		}
		return retNode;
	}

	/**
	 * 返回以node为根的二分搜索树的最小值所在的结点
	 *
	 * @param node 以node为根的二分搜索树
	 * @return 以node为根的二分搜索树的最小值所在的结点
	 */
	private Node minimum(Node node) {
		if (node.left == null) {
			return node;
		}
		return minimum(node.left);
	}

	public boolean contains(K key) {
		return getNode(root, key) != null;
	}

	public V get(K key) {
		Node node = getNode(root, key);
		return node == null ? null : node.value;
	}

	public void set(K key, V value) {
		Node node = getNode(root, key);
		if (node == null) {
			throw new IllegalArgumentException(key + "doesn't exist!");
		}
		node.value = value;
	}

	public int getSize() {
		return size;
	}


	public boolean isEmpty() {
		return size == 0;
	}

	private class Node {
		/**
		 * 键
		 */
		public K key;
		/**
		 * 值
		 */
		public V value;
		/**
		 * 左子树地址域
		 */
		public Node left;
		/**
		 * 右子树地址域
		 */
		public Node right;
		/**
		 * 记录当前节点所处的高度值
		 */
		public int height;

		public Node(K key, V value) {
			this.key = key;
			this.value = value;
			this.left = null;
			this.right = null;
			height = 1;
		}
	}
}

测试用例

package com.holelin.tree;

import com.holelin.map.BSTMap;
import com.holelin.util.FileOperation;

import java.util.ArrayList;
import java.util.Collections;

/**
 * ClassName: AVLTreeTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/17
 */

public class AVLTreeTest {
	public static void main(String[] args) {
		String path = "src/res/Pride-and-prejudice.txt";
		System.out.println("Pride and prejudice ");
		ArrayList<String> words = new ArrayList<>();
		if (FileOperation.readFile(path, words)) {
			// 对words排序 使BST退化为链表
			Collections.sort(words);
			long startTime = System.nanoTime();
			BSTMap<String, Integer> bstMap = new BSTMap<>();
			for (String word :
					words) {
				if (bstMap.contains(word)) {
					bstMap.set(word, bstMap.get(word) + 1);
				} else {
					bstMap.add(word, 1);
				}
			}
			for (String word :
					words) {
				bstMap.contains(word);
			}

			long endTime = System.nanoTime();
			double time = (endTime - startTime) / 1000000000.0;
			System.out.println("Total different words :" + bstMap.getSize());
			System.out.println("BSTMap: " + time + "s");
			// -----

			startTime = System.nanoTime();
			AVLTree<String, Integer> avlTree = new AVLTree<>();
			for (String word : words
			) {
				if (avlTree.contains(word)) {
					avlTree.set(word, avlTree.get(word) + 1);
				} else {
					avlTree.add(word, 1);
				}
			}
			for (String word :
					words) {
				avlTree.contains(word);
			}
			System.out.println("Total different words :" + avlTree.getSize());
			for (String word :
					words) {
				avlTree.remove(word);
				if (!avlTree.isBalanced() || !avlTree.isBalanced()) {
					throw new IllegalArgumentException("Error");
				}
			}
			endTime = System.nanoTime();
			time = (endTime - startTime) / 1000000000.0;
			System.out.println("AVLMap: " + time + "s");

		}
	}
}

红黑树

package com.holelin.tree;


/**
 * ClassName: RedBlackTree
 * 红黑树
 * 性质:
 * 1. 每个节点或者是红色的,或者是黑色的
 * 2. 根节点是黑色的
 * 3. 每一个叶子节点(最后的空节点)是黑色的
 * 4. 如果一个节点是红色的,那么它的孩子节点都是黑色的
 * 5. 从任意一个节点到叶子节点,经过的黑色节点是一样多的.
 * <p>
 * <p>
 * 红黑树的另一种定义是满足下列条件的二叉查找树:
 * ⑴红链接均为左链接.
 * ⑵没有任何一个结点同时和两条红链接相连.(这样会出现4-节点)
 * ⑶该树是完美黑色平衡的,即任意空链接到根结点的路径上的黑链接数量相同.
 * </p>
 * 2-3树中添加一个新元素
 * 或者添加进2-节点,形成3-节点
 * 或者添加进3-节点,暂时形成一个4-节点
 * https://www.cnblogs.com/tiancai/p/9072813.html
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/18
 */

public class RedBlackTree<K extends Comparable<K>, V> {
    private Node root;
    private int size;

    public RedBlackTree() {
        root = null;
        size = 0;
    }

    /**
     * 判断节点的颜色
     *
     * @param node 带判断的节点
     * @return 节点的颜色
     */
    private boolean isRed(Node node) {
        if (node == null) {
            return BLACK;
        }
        return node.color;
    }

    /**
     * 对以node为根的树进行左旋转
     * -----node                     x
     * ----/   \     左旋转         /  \
     * --T1   x   --------->   node   T3
     * -------/ \              /   \
     * ------T2 T3            T1   T2
     *
     * @param node 以node为根的树
     * @return 左旋转之后新的根节点
     */
    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;
    }

    /**
     * 对以node为根的树进行右旋转
     * ---node                   x
     * ---/   \     右旋转       /  \
     * --x    T2   ------->   y   node
     * -/ \                       /  \
     * y  T1                     T1  T2
     *
     * @param node 以node为根的树
     * @return 右旋转之后新的根节点
     */
    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;
    }

    /**
     * 对以node为根的树进行颜色翻转
     *
     * @param node 以node为根的树
     */
    private void flipColors(Node node) {
        node.color = RED;
        node.left.color = BLACK;
        node.right.color = BLACK;
    }

    /**
     * 向红黑树添加元素
     *
     * @param key   键
     * @param value 值
     */
    public void add(K key, V value) {
        root = add(root, key, value);
        // 保持根节点为黑色节点
        root.color = BLACK;
    }

    /**
     * 向以node为根的红黑树中插入元素(key,value),递归算法
     *
     * @param node  以node为根的红黑树
     * @param key   键
     * @param value 值
     * @return 返回插入新节点后红黑树的根
     */
    private Node add(Node node, K key, V value) {

        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;
        }
        // 右孩子为红色,左孩子不为红色 进行左旋转
        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);
        }
        return node;
    }

    private Node getNode(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (node.key.compareTo(key) == 0) {
            return node;
        } else if (node.key.compareTo(key) < 0) {
            return getNode(node.left, key);
        } else {
            return getNode(node.right, key);
        }
    }

    public V remove(K key) {
        Node node = getNode(root, key);
        if (node != null) {
            root = remove(root, key);
            return root.value;
        }
        return null;
    }


    private Node remove(Node node, K key) {
        if (node == null) {
            return null;
        }
        if (key.compareTo(node.key) < 0) {
            // 到node左子树寻找
            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 (node.left == null) {
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;
            }
            // 待删除节点右子树为空的情况
            if (node.right == null) {
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;
            }
            // 带删除节点左右子树均不为空的情况
            // 找到比带删除节点大的最小的节点,即待删除节点右子树的最小节点
            // 用这个节点顶替待删除节点的位置
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            successor.left = node.left;
            node.left = node.right = null;
            return successor;
        }
    }

    /**
     * 返回以node为根的二分搜索树的最小值所在的结点
     *
     * @param node 以node为根的二分搜索树
     * @return 以node为根的二分搜索树的最小值所在的结点
     */
    private Node minimum(Node node) {
        if (node.left == null) {
            return node;
        }
        return minimum(node.left);
    }

    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后的新的二分搜索树的根
     *
     * @param node 以node为根的二分搜索树
     * @return 返回删除节点后的新的二分搜索树的根
     */
    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 boolean contains(K key) {
        return getNode(root, key) != null;
    }


    public V get(K key) {
        Node node = getNode(root, key);
        return node == null ? null : node.value;
    }


    public void set(K key, V value) {
        Node node = getNode(root, key);
        if (node == null) {
            throw new IllegalArgumentException(key + "doesn't exist!");
        }
        node.value = value;
    }


    public int getSize() {
        return size;
    }


    public boolean isEmpty() {
        return size == 0;
    }

    private static final boolean RED = true;
    private static final boolean BLACK = false;

    private class Node {
        /**
         * 键
         */
        public K key;
        /**
         * 值
         */
        public V value;
        /**
         * 左子树地址域
         */
        public Node left;
        /**
         * 右子树地址域
         */
        public Node right;
        /**
         * 标记红黑节点
         */
        public boolean color;

        public Node(K key, V value) {
            this.key = key;
            this.value = value;
            this.left = null;
            this.right = null;
            this.color = RED;
        }
    }

}

测试用例

package com.holelin.tree;

import com.holelin.map.BSTMap;
import com.holelin.util.FileOperation;

import java.util.ArrayList;
import java.util.Random;

/**
 * ClassName: RedBlackTreeTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/19
 */

public class RedBlackTreeTest {
	public static void main(String[] args) {
//		testTree();
		String path = "src/res/Pride-and-prejudice.txt";
		System.out.println("Pride and prejudice ");
		ArrayList<String> words = new ArrayList<>();
		if (FileOperation.readFile(path, words)) {
			// 对words排序 使BST退化为链表
			// Collections.sort(words);
			long startTime = System.nanoTime();
			RedBlackTree<String, Integer> redBlackTree = new RedBlackTree<>();
			for (String word : words) {
				if (redBlackTree.contains(word)) {
					redBlackTree.set(word, redBlackTree.get(word) + 1);
				} else {
					redBlackTree.add(word, 1);
				}
			}
			for (String word : words) {
				redBlackTree.contains(word);
			}

			long endTime = System.nanoTime();
			double time = (endTime - startTime) / 1000000000.0;
			System.out.println("Total different words :" + redBlackTree.getSize());
			System.out.println("RedBlackTree: " + time + "s");


			startTime = System.nanoTime();
			AVLTree<String, Integer> avlTree = new AVLTree<>();
			for (String word : words) {
				if (avlTree.contains(word)) {
					avlTree.set(word, avlTree.get(word) + 1);
				} else {
					avlTree.add(word, 1);
				}
			}
			for (String word : words) {
				avlTree.contains(word);
			}
			endTime = System.nanoTime();
			time = (endTime - startTime) / 1000000000.0;
			System.out.println("AVLMap: " + time + "s");

			startTime = System.nanoTime();
			HashTable<String, Integer> hashTable = new HashTable<>();

			for (String word : words) {
				if (hashTable.contains(word)) {
					hashTable.set(word, hashTable.get(word) + 1);
				} else {
					hashTable.add(word, 1);
				}
			}
			for (String word : words) {
				hashTable.contains(word);
			}
			endTime = System.nanoTime();
			time = (endTime - startTime) / 1000000000.0;
			System.out.println("HashTable: " + time + "s");


		}
	}

	public static void testTree() {
		int n = 20000000;
		Random random = new Random();
		ArrayList<Integer> testData = new ArrayList<>();
		for (int i = 0; i < n; i++) {
			testData.add(random.nextInt(Integer.MAX_VALUE));
//			testData.add(n);
		}
		long startTime = System.nanoTime();

		BSTMap<Integer, Integer> bstMap = new BSTMap<>();
		for (Integer x : testData
		) {
			bstMap.add(x, null);
		}
		long endTime = System.nanoTime();
		double time = (endTime - startTime) / 1000000000.0;
		System.out.println("bstMap: " + time + "s");
		startTime = System.nanoTime();

		AVLTree<Integer, Integer> avlTree = new AVLTree<>();
		for (Integer x : testData
		) {
			avlTree.add(x, null);
		}
		endTime = System.nanoTime();
		time = (endTime - startTime) / 1000000000.0;
		System.out.println("avlTree: " + time + "s");
		startTime = System.nanoTime();

		RedBlackTree<Integer, Integer> redBlackTree = new RedBlackTree<>();
		for (Integer x : testData
		) {
			redBlackTree.add(x, null);
		}
		endTime = System.nanoTime();
		time = (endTime - startTime) / 1000000000.0;
		System.out.println("redBlackTree: " + time + "s");

	}
}

基于数组的线段树

package com.holelin.tree;

/**
 * ClassName: SegmentTree
 * 基于数组的线段树
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/14
 */

public class SegmentTree<E> {
	/**
	 * 传入数组的副本
	 */
	private E[] data;
	/**
	 * 使用线段树的方式存储元素
	 */
	private E[] tree;

	private Merger<E> merger;

	public SegmentTree(E[] arr, Merger<E> merger) {
		this.merger = merger;
		data = (E[]) new Object[arr.length];
		// 将传入的数组复制一个副本
		for (int i = 0; i < arr.length; i++) {
			data[i] = arr[i];
		}
		// 存储arr.length长度的数据构建为线段树需要4*arr.length长度的数组
		tree = (E[]) new Object[4 * arr.length];
		buildSegmentTree(0, 0, data.length - 1);
	}

	/**
	 * 在treeIndex的位置创建表示区间[l...r]的线段树
	 *
	 * @param treeIndex 当前要创建的线段数根节点的索引
	 * @param l         要创建的区间的左边界
	 * @param r         要创建的区间的右边界
	 */
	private void buildSegmentTree(int treeIndex, int l, int r) {
		// 递归结束条件
		if (l == r) {
			tree[treeIndex] = data[l];
			return;
		}
		// 获取treeIndex的左孩子的索引
		int leftTreeIndex = leftChild(treeIndex);
		// 获取treeIndex的右孩子的索引
		int rightTreeIndex = rightChild(treeIndex);

		// 创建该节点的左右子树
		int mid = l + (r - l) / 2;
		// 创建左子树
		buildSegmentTree(leftTreeIndex, l, mid);
		// 创建右子树
		buildSegmentTree(rightTreeIndex, mid + 1, r);

		// 对区间设置含义(融合左右子树)
		tree[treeIndex] = merger.merge(tree[leftTreeIndex], tree[rightTreeIndex]);
	}

	/**
	 * 返回区间[queryL,queryR]的值
	 *
	 * @param queryL 要查询区间的左边界
	 * @param queryR 要查询区间的左边界
	 * @return 区间[queryL, queryR]的值
	 */
	public E query(int queryL, int queryR) {
		// 边界检查
		if (queryL < 0 || queryL >= data.length ||
				queryR < 0 || queryR >= data.length || queryL > queryR) {
			throw new IllegalArgumentException("Index is illegal.");
		}
		return query(0, 0, data.length - 1, queryL, queryR);
	}

	/**
	 * 在当前treeIndex为根的线段树中[l,r]的范围中,搜索区间[queryL,queryR]的值
	 *
	 * @param treeIndex 当前树的根节点的索引
	 * @param l         当前节点所表示的区间的左边界
	 * @param r         当前节点所表示的区间的右边界
	 * @param queryL    要查询的区间的左边界
	 * @param queryR    要查询的区间的左边界
	 * @return 区间[queryL, queryR]的值
	 */
	private E query(int treeIndex, int l, int r, int queryL, int queryR) {
		// 递归介结束条件
		if (l == queryL && r == queryR) {
			return tree[treeIndex];
		}
		int mid = l + (r - l) / 2;
		int leftTreeIndex = leftChild(treeIndex);
		int rightTreeIndex = rightChild(treeIndex);
		if (queryL >= mid + 1) {
			// 要查询的左边界大于区间[l,r]的中间位置 -- 说明[l,mid]不需要查询
			// 直接查询[mid+1,r]区间
			return query(rightTreeIndex, mid + 1, r, queryL, queryR);
		} else if (queryR <= mid) {
			// 要查询的右边界小于区间[l,r]的中间位置 -- 说明[mid+1,r]不需要查询
			// 否则查询[l,mid]区间
			return query(leftTreeIndex, l, mid, queryL, queryR);
		} else {
			// 此时这种情况表示:要查询的区间[queryL,queryR] 一部分在[l,mid]区间中,一部分在[mid+1,r]区间中
			E leftResult = query(leftTreeIndex, l, mid, queryL, mid);
			E rightResult = query(rightTreeIndex, mid + 1, r, mid + 1, queryR);
			return merger.merge(leftResult, rightResult);
		}

	}

	/**
	 * 将index位置的值,更新为e
	 *
	 * @param index 索引为index
	 * @param e     新的值
	 */
	public void set(int index, E e) {
		if (index < 0 || index >= data.length) {
			throw new IllegalArgumentException("Index is illegal");
		}
		data[index] = e;
		// 跟新tree
		set(0, 0, data.length - 1, index, e);

	}

	/**
	 * 在以treeIndex为根的线段树中更新index的值为e
	 *
	 * @param treeIndex 当前树的根节点的索引
	 * @param l         当前节点所表示的区间的左边界
	 * @param r         当前节点所表示的区间的右边界
	 * @param index     待更新的位置的索引
	 * @param e         新的元素的值
	 */
	private void set(int treeIndex, int l, int r, int index, E e) {
		if (l == r) {
			tree[treeIndex] = e;
			return;
		}
		int mid = l + (r - l) / 2;
		int leftTreeChild = leftChild(treeIndex);
		int rightTreeChild = rightChild(treeIndex);
		if (index >= mid + 1) {
			set(rightTreeChild, mid + 1, r, index, e);
		} else {
			set(leftTreeChild, l, mid, index, e);
		}

		tree[treeIndex] = merger.merge(tree[leftTreeChild], tree[rightTreeChild]);
	}

	/**
	 * 返回完全二叉树的数组表示中,一个索引表示的元素的左孩子节点的索引
	 * tips: 索引从0开始
	 *
	 * @param index 查找左孩子节点的索引
	 * @return 所查节点的左孩子节点的索引
	 */
	private int leftChild(int index) {
		return index * 2 + 1;
	}

	/**
	 * 返回完全二叉树的数组表示中,一个索引表示的元素的右孩子节点的索引
	 * tips: 索引从0开始
	 *
	 * @param index 查找右孩子节点的索引
	 * @return 所查节点的右孩子节点的索引
	 */
	private int rightChild(int index) {
		return index * 2 + 2;
	}

	/**
	 * 获取线段树中元素的个数
	 *
	 * @return 线段树中元素的个数
	 */
	public int getSize() {
		return data.length;
	}

	/**
	 * 获取索引为index的元素值
	 *
	 * @param index 索引为index的元素
	 * @return 索引为index的元素值
	 */
	public E get(int index) {
		if (index < 0 || index >= data.length) {
			throw new IllegalArgumentException("Index is illegal.");
		}

		return data[index];
	}

	@Override
	public String toString() {
		StringBuilder res = new StringBuilder();
		res.append('[');
		for (int i = 0; i < tree.length; i++) {
			if (tree[i] != null) {
				res.append(tree[i]);
			} else {
				res.append("null");
			}
			if (i != tree.length - 1) {
				res.append(", ");
			}
		}
		res.append(']');
		return res.toString();
	}
}

测试用例

• Merger

package com.holelin.tree;

public interface Merger<E> {
	E merge(E a, E b);

}

package com.holelin.tree;

/**
 * ClassName: SegmentTreeTest
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/14
 */

public class SegmentTreeTest {
	public static void main(String[] args) {
		Integer[] nums = {-2, 0, 3, -5, 2, -1};
		SegmentTree<Integer> segmentTree = new SegmentTree<>(nums, new Merger<Integer>() {
			@Override
			public Integer merge(Integer a, Integer b) {
				return a + b;
			}
		});
		System.out.println(segmentTree);
		System.out.println(segmentTree.query(0, 2));
		System.out.println(segmentTree.query(2, 5));
		System.out.println(segmentTree.query(0, 5));
	}

}

字典树(前缀树)

package com.holelin.tree;

import java.util.TreeMap;

/**
 * ClassName: Trie
 * 字典树(前缀树)
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class Trie {
	private Node root;
	private int size;

	public Trie() {
		root = new Node();
		size = 0;
	}

	/**
	 * 查询在Trie中是否有以单词prefix为前缀
	 *
	 * @param prefix 前缀
	 * @return 存在返回true;反之返回false;
	 */
	public boolean isPrefix(String prefix) {
		Node cur = root;
		for (int i = 0; i < prefix.length(); i++) {
			char c = prefix.charAt(i);
			if (cur.next.get(c) == null) {
				return false;
			}
			cur = cur.next.get(c);
		}
		return true;
	}


	/**
	 * 查询Trie中是否包含word这个单词
	 * (非递归写法)
	 *
	 * @param word 待查询的单词
	 * @return 存在返回true;反之返回false;
	 */
	public boolean contains(String word) {
		Node cur = root;
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);
			if (cur.next.get(c) == null) {
				return false;
			}
			cur = cur.next.get(c);
		}
		return cur.isWord;
	}


	/**
	 * 向Trie中添加新的单词
	 * (非递归写法)
	 *
	 * @param word 新的单词
	 */
	public void add(String word) {
		Node cur = root;
		// 对word进行拆分
		for (int i = 0; i < word.length(); i++) {
			char c = word.charAt(i);
			// 判断cur的下一个节点的Map中是否存在c
			// 不存在c则创建新节点
			if (cur.next.get(c) == null) {
				cur.next.put(c, new Node());
			}
			cur = cur.next.get(c);
		}
		// 判断到最后,发现当前位置的isWord==false,则表示该word为新的单词,改变isWord的值,增加size
		// 若isWord==true,则表示该word已经存在,则不需要进行其他操作
		if (!cur.isWord) {
			cur.isWord = true;
			size++;
		}
	}

	/**
	 * 获取Trie中元素的个数
	 *
	 * @return Trie中元素的个数
	 */
	public int getSize() {
		return size;
	}

	/**
	 * 判断Trie是否为空
	 *
	 * @return 为空返回true;反之返回false
	 */
	public boolean isEmpty() {
		return size == 0;
	}

	private class Node {
		/**
		 * 标识从根到当前节点的组成的字符串是否为单词
		 */
		public boolean isWord;
		/**
		 * 指向下一(多)个节点
		 */
		public TreeMap<Character, Node> next;

		public Node(boolean isWord) {
			this.isWord = isWord;
			next = new TreeMap<>();
		}

		public Node() {
			this(false);
		}
	}
  
}

测试用例

package com.holelin.tree;

import com.holelin.set.BSTSet;
import com.holelin.util.FileOperation;

import java.util.ArrayList;

/**
 * ClassName: TrieTest
 * Trie测试类
 *
 * @author HoleLin
 * @version 1.0
 * @date 2019/2/16
 */

public class TrieTest {
	public static void main(String[] args) {
		String path = "src/res/Pride-and-prejudice.txt";

		System.out.println("Pride-and-prejudice");
		ArrayList<String> words = new ArrayList<>();
		if (FileOperation.readFile(path, words)) {
			long startTime = System.nanoTime();
			BSTSet<String> set = new BSTSet<>();
			for (String word :
					words) {
				set.add(word);
			}
			for (String word :
					words) {
				set.contains(word);
			}

			long endTime = System.nanoTime();
			double time = (endTime - startTime) / 1000000000.0;
			System.out.println("Total different words :" + set.getSize());
			System.out.println("BSTSet: " + time + "s");
			// -----

			startTime = System.nanoTime();
			Trie trie = new Trie();
			for (String word :
					words) {
				trie.add(word);
			}
			for (String word :
					words) {
				trie.contains(word);
			}

			endTime = System.nanoTime();
			time = (endTime - startTime) / 1000000000.0;
			System.out.println("Total different words :" + trie.getSize());
			System.out.println("Trie: " + time+ "s");

		}

	}
}