本文共 38390 字，大约阅读时间需要 127 分钟。

数据结构-树形结构

• 数组ArrayList
• 链表LinkedList
• 栈Stack
• 队列Queue
• 哈希表(散列表)(单独摘出来)

• 树Tree
• 二叉树BinaryTree
• 二叉搜索树BinarySearchTree
• 平衡二叉树BalanceBinarySearchTree
• B树
• AVL树
• 红黑树
• 哈夫曼树
• Trie树

• 树Tree
• 二叉树BinaryTree
• 二叉搜索树BinarySearchTree
• 平衡二叉树BalanceBinarySearchTree
• B树
• AVL树
• 红黑树
• 哈夫曼树
• Trie树

一、树形结构

1. 树的基本概念

• 一棵树可以没有任何节点，称为空树

• 一棵树可以只有1个节点，也就是只有根节点

• 子树、左子树、右子树

• **节点的度：**子树的个数

• **树的度：**所有节点度中的最大值

• **叶子节点：**度为0的节点

• **非叶子节点：**度不为0的节点

• **层数：**根结点在第1层，根结点的子节点在第2层，以此类推。（有些教程也从第0层开始计算）

• **节点的深度：**从根结点到当前节点的唯一路径上的节点总数

• **节点的高度：**从当前节点到最远节点的路径上的节点总数

• **树的深度：**所有节点深度中的最大值

• **树的高度：**所有节点告诉中的最大值

• 树的深度等于树的高度

• **有序树：**树中任意节点的子节点之间有顺序关系

• 无序树：树中任意节点的子节点之间没有顺序关系

• **森林：**由m棵互不相交的树组成的集合

二、 二叉树

二叉树的特点：

• 每个节点的度最大为2(最多拥有2棵子树)
• 左子树和右子树是有顺序的
• 即使某节点只有一颗子树，也要区分左右子树

1.二叉树的性质

• 非空二叉树的第i层，最多有2^(i-1)个节点
• 在高度为h的二叉树最多有(2^h)-1个节点
• 对于任何一棵非空二叉树，如果叶子节点个数为n0, 度为2的节点个数为n2, 则有n0 = n2 + 1;

2.满二叉树

满二叉树：最后一层节点的度都为0，其它节点的度都为2.

3.完全二叉树

完全二叉树：对节点从上至下、左至右开始编号，其所有编号都能与相同高度的满二叉树中的编号对应。

• 叶子节点只会出现最后2层，最后一层的叶子节点都靠左对齐
• 完全二叉树从根结点至倒数第2层是一棵满二叉树
• 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。

面试题：

如果一棵完全二叉树有768个节点，求叶子节点的个数

• 叶子节点个数为n0 = floor((n+1)/2)
• 非叶子节点个数为n1+n2=floor(n/2)

4. 构建一棵二叉排序树

• 在BinaryTree中主要有以下方法
  • size 树节点个数
  • root 根节点
  • Node 节点类
    • root()
    • left()
    • right()
    • string()

package com.lcz.tree;import com.lcz.printer.BinaryTreeInfo;/** * 二叉树 * @author LvChaoZhang * */public class BinaryTree
   
     implements BinaryTreeInfo{
   	/**	 * 树的两个成员变量	 */	protected int size;	protected Node
    
      root;		public int size() {
   		return size;	}		public boolean isEmpty() {
   		return size==0;	}			/**	 * 树的结点类	 * @author LvChaoZhang	 *	 * @param 
     
      	 */	protected static class Node
      
       {
   		E element;		Node
       
         left;		Node
        
          right; Node
         
           parent; public Node(E element,Node
          
            parent) { this.element = element; this.parent = parent; } public boolean isLeaf() { return left==null && right==null; } public boolean hasTwoChildren() { return left!=null&&right!=null; } } @Override public Object root() { // TODO Auto-generated method stub return root; } @Override public Object left(Object node) { // TODO Auto-generated method stub return ((Node
           
            )node).left; } @Override public Object right(Object node) { // TODO Auto-generated method stub return ((Node
            
             )node).right; } @Override public Object string(Object node) { Node
             
               myNode = (Node
              
               )node; String parentString = "null"; if (myNode.parent != null) { parentString = myNode.parent.element.toString(); } return myNode.element + "_p(" + parentString + ")"; }}
              
             
            
           
          
         
        
       
      
     
    
   

• 在二叉搜索树中中包含创建一棵树的操作

package com.lcz.tree;/** * 二叉搜索树 * @author LvChaoZhang * */import java.util.Comparator;public class BinarySearchTree
   
     extends BinaryTree
    
      {
   	// 添加一个比较器	private Comparator
     
       comparator;		// 构造函数	public BinarySearchTree() {
   		this(null);	}		public BinarySearchTree(Comparator
      
        comparator) {
   		this.comparator = comparator;	}		// 对树进行添加结点即构建一个二叉搜索树	public void add(E element) {
   		// 添加第一个结点		if(root==null) {
   			root = new Node<>(element,null);			size++;			return;		}		//添加的不是第一个结点		Node
       
         parent = root;		Node
        
          node = root; // 找到其父节点 int cmp = 0; do { cmp = compare(element,node.element); parent = node; if(cmp>0) { node = node.right; }else if(cmp<0) { node = node.left; }else { // 如果要插入的结点跟树中的结点，覆盖其元素 node.element = element; return; } }while(node!=null); // 添加进去 Node
         
           newNode = new Node<>(element,parent); if(cmp>0) { parent.right = newNode; }else { parent.left = newNode; } size++; } // 比较添加的两个元素大小 private int compare(E e1,E e2) { if(comparator!=null) { return comparator.compare(e1, e2); } return ((Comparable
          
           )e1).compareTo(e2); } // 不允许添加null结点 private void elementNotNullCheck(E element) { if(element==null) { throw new IllegalArgumentException("element must not be null"); } }}
          
         
        
       
      
     
    
   

如果二叉树添加一个对象，如何进行比较呢？

• 一是对其类本身使其实现Comparable这个接口，并对compareTo这个方法实现

  public class Person implements Comparable
        
         {
        @Override	public int compareTo(Person e) {
        //		if (age > e.age) return 1;//		if (age < e.age) return -1;//		return 0;		return age - e.age;	}}
        

• 二是对以匿名内部类的方式传入二叉搜索树的Comparator这个接口方法

BinarySearchTree
    
      bst2 = new BinarySearchTree<>(new Comparator
     
      () {
    			public int compare(Person o1, Person o2) {
    				return o2.getAge() - o1.getAge();			}		});
     
    

5. 二叉树的遍历

5.1 前序遍历(Preorder Traversal)

递归方式

// 递归方式前序遍历	public void preorder(Visitor
   
     visitor) {
   		if(visitor==null)return;		preorder(root,visitor); 	}	private void preorder(Node
    
      node,Visitor
     
       visitor) {
   		if(node==null || visitor.stop)return;				visitor.stop = visitor.visit(node.element);		preorder(node.left,visitor);		preorder(node.right,visitor);			}		// 对元素的处理	public static abstract class Visitor
      
       {
   		boolean stop;		protected abstract boolean visit(E element);	}
      
     
    
   

非递归方式

// 非递归方式前序遍历		public void preorder() {
   			preorder(root);		 		private void preorder(Node
   
     node) {
   			// 用栈			Stack
    
     
      > stack = new Stack<>();			while(!stack.isEmpty() || node!=null) {
   				if(node!=null) {
   					System.out.print( .element + " ");					stack.push(node);					node = node.left;				}else {
   					node = stack.pop().right;				}			}		}
     
    
   

5.2 中序遍历(Inorder Traversal)

递归方式

// 递归方式中序遍历	public void inorder(Visitor
   
     visitor) {
   		if(visitor==null)return;		inorder(root,visitor); 	}	private void inorder(Node
    
      node,Visitor
     
       visitor) {
   		if(node==null || visitor.stop)return;		inorder(node.left,visitor);		visitor.stop = visitor.visit(node.element);		inorder(node.right,visitor);			}
     
    
   

非递归方式

// 非递归方式中序遍历		public void inorder() {
   			inorder(root); 		}		private void inorder(Node
   
     root) {
   			Stack
    
     
      > stack = new Stack<>();			Node
      
        cur = root;			Node
       
         node = null;			while(cur!=null||!stack.isEmpty()) {
   				if(cur!=null) {
   					stack.push(cur);					cur = cur.left;				}else {
   					node = stack.pop();					System.out.print(node.element+" ");					cur = node.right;				}			}		}
       
      
     
    
   

5.3 后序遍历(Postorder Traversal)

递归方式

// 递归方式后序遍历		public void postorder(Visitor
   
     visitor) {
   			if(visitor==null)return;			postorder(root,visitor); 		}		private void postorder(Node
    
      node,Visitor
     
       visitor) {
   			if(node==null || visitor.stop)return;			postorder(node.left,visitor);			postorder(node.right,visitor);			visitor.stop = visitor.visit(node.element);					}
     
    
   

非递归方式

// 递归方式后序遍历		public void postorder() {
   			postorder(root);		}		private void postorder(Node
   
     root) {
   			Stack
    
     
      > stack = new Stack<>();			// 遍历结点			Node
      
        cur = root;			Node
       
         pre = null;			while(!stack.isEmpty()||cur!=null) {
   				if(cur!=null) {
   					stack.push(cur);					cur = cur.left;				}else {
   					// 若栈顶元素右孩子为空或者当前最后访问过的结点，则出栈，同时pre为栈顶元素					if(stack.peek().right==null || stack.peek().right==pre) {
   						pre  = stack.pop();						System.out.print(pre.element + " ");					}else {
   						// 栈顶右孩子未访问，遍历其右孩子						cur = stack.peek().right;					}				}			}		}
       
      
     
    
   

5.4 层序遍历(Level Order Traversal)

// 层序遍历		public void levelOrder() {
   			levelOrder(root);		}		private void levelOrder(Node
   
     node) {
   			Queue
    
     
      > queue = new LinkedList<>();			queue.offer(node);			while(!queue.isEmpty()) {
   				node = queue.poll();				System.out.print(node.element+" ");				if(node.left!=null) {
   					queue.offer(node.left);				}								if(node.right!=null) {
   					queue.offer(node.right);				}			}		}
     
    
   

6. 遍历的应用

6.1 翻转二叉树

/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */class Solution {
       public TreeNode invertTree(TreeNode root) {
           // 前序遍历		if(root==null)			return root;		TreeNode temp = root.left;		root.left = root.right;		root.right = temp;		invertTree(root.left);		invertTree(root.right);		return root;    }}

6.2判断是否为完全二叉树

// 判断一棵树是否为完全二叉树		public  boolean isComplete() {
   			Queue
   
    
     > queue = new LinkedList<>();			queue.offer(root);						boolean leaf = true;			while(!queue.isEmpty()) {
   				Node
     
       node = queue.poll();				if(leaf&&!node.isLeaf()) {
   					return false;				}								if(node.left!=null) {
   					queue.offer(node.left);				}else if(node.right!=null) {
   					return false;				}												if(node.right!=null) {
   					queue.offer(node.right);				}else {
   					leaf = true;				}			}			return true;		}
     
    
   

7. 二叉树的前驱和后继

7.1 前驱节点 predecessor

• 条件：node.left!=null

• 举例：6,13,8

• predecessor=node.left.right.right.right…

• 终止条件：right为null

• 条件：node.left==null&&node.parent!=null

• 举例：7,11,9,1

• predecessor=node.parent.parent.parent…

• 终止条件：node在parent的右子树

• 条件：node.left == null&&node.parent==null

• 没有前驱节点

• 举例：没有左子树的根结点

// 前驱结点		protected Node
   
     predessor(Node
    
      node){
   			if(node==null)				return null;			// 前驱结点在左子树中			Node
     
       p = node.left;			if(p!=null) {
   				while(p.right!=null) {
   					p = p.right;				}				return p;			}			// 从父节点、祖父节点中寻找前驱结点			while(node.parent!=null&&node==node.parent.left) {
   				node=node.parent;			}						return node.parent;		}
     
    
   

7.2 后继节点 successor

• 条件：node.right!=null

• 举例：1,8,4

• predecessor=node.right.left.left.left…

• 终止条件：left为null

• 条件：node.right==null&&node.parent!=null

• 举例：7,6,3,11

• predecessor=node.parent.parent.parent…

• 终止条件：node在parent的左子树

• 条件：node.left == null&&node.parent==null

• 没有前驱节点

• 举例：没有右子树的根结点

7.3 根据遍历重构二叉树

以下结果可以保证重构出唯一的一棵二叉树。

• 前序遍历+中序遍历
• 后序遍历+中序遍历

7.3.1 前序遍历+中序遍历构造二叉树

package com.lcz.leetcode;/** * 从前序和中序遍历序列构造二叉树 * @author LvChaoZhang * */import java.util.*;public class Leetcode105 {
   	class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(int x){
   			val = x;		}	}	 private HashMap
   
     hashMap;	 private TreeNode myBuildTree(int[] preorder,int[] inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right) {
   		 if(preorder_left>preorder_right) {
   			 return null;		 }		 // 前序遍历的第一个结点是根节点		 int preorder_root = preorder_left;		 // 中序遍历中定位根节点		 int inorder_root = hashMap.get(preorder[preorder_root]);		 		 // 根节点建立		 TreeNode root = new TreeNode(preorder[preorder_root]);		 // 得到左节点数量		 int size_left_subtree = inorder_root-inorder_left;		 root.left = myBuildTree(preorder, inorder, preorder_left+1, preorder_left+size_left_subtree, inorder_left, inorder_root-1);		 root.right = myBuildTree(preorder, inorder, preorder_left+size_left_subtree+1, preorder_right, inorder_root+1, inorder_right);		 return root;		 	 }	 public TreeNode buildTree(int[] preorder, int[] inorder) {
   		 int n = preorder.length;		 // 构造哈希映射，快速定位根节点		 hashMap = new HashMap
    
     ();		 for(int i=0;i
    
   

7.3.2 后序遍历+中序遍历构造二叉树

package com.lcz.leetcode;/** * 从中序与后续遍历序列构造二叉树 * @author LvChaoZhang * */import java.util.*;public class Leetcode106 {
   	class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(int x){
   			val = x;		}	}	private HashMap
   
     hashMap;		private TreeNode myBuildTree(int[] inorder,int[] postorder,int inorder_left,int inorder_right,int postorder_left,int postorder_right) {
   		if(inorder_left>inorder_right) {
   			return null;		}		//  从后序遍历中找到根节点		int postorder_root = postorder_right;		// 从中序遍历中找到根节点		int inorder_root = hashMap.get(postorder[postorder_right]);		// 构建根节点		TreeNode root = new TreeNode(postorder[postorder_right]);		// 计算左节点的数量		int left_size_subtree = inorder_root-inorder_left;				// 递归构建		root.left = myBuildTree(inorder, postorder, inorder_left, inorder_root-1, postorder_left, postorder_left+left_size_subtree-1);		root.right = myBuildTree(inorder, postorder, inorder_root+1, inorder_right, postorder_left+left_size_subtree, postorder_right-1);		return root;	}		public TreeNode buildTree(int[] inorder, int[] postorder) {
   		int n = inorder.length;		// 构建哈希映射		hashMap = new HashMap<>();		for(int i=0;i
   

三、 二叉搜索树(Binary Search Tree)

• 二叉搜索树是二叉树的一种，是应用非常广泛的一种二叉树，英文简称为BST

• 又被称为：二叉查找树、二叉排序树

• 任意一个节点的值都大于其左子树所有节点的值

• 任意一个节点的值都小于其右子树所有节点的值

• 它的左右子树也是一棵二叉搜索树

• 二叉搜索树可以大大提高搜索数据的效率

• 二叉搜索树存储的元素必须具备可比较性

• 比如int double等

• 如果是自定义类型，需要指定比较方式

• 不允许为null

1. 二叉搜索树的接口设计

• int size(); // 元素的数量
• boolean isEmpty(); //是否为空
• void clear(); //清空所有元素
• void add(); // 添加元素
• void remove(); //删除元素
• boolean contains(E element); //是否包含某元素

元素的比较方案设计：

• 允许外界传入一个Comparator 自定义比较方案
• 如果没有传入Comparator，强制认定元素实现了Comparable接口

2. 二叉搜索树重要接口实现

2.1 根据元素内容获取接口

// 元素是否包含在其中	public boolean contains(E element) {
   		return node(element)!=null;	}		// 给定元素返回节点	private Node
   
     node(E element){
   		Node
    
      node = root;		while(node!=null) {
   			int cmp = compare(element,node.element);			if(cmp==0)				return node;			if(cmp>0) {
   				node = node.right;			}else {
   				node = node.left;			}		}		return null;	}
    
   

2.2 删除节点

2.2.1 删除节点-叶子节点

node == node.parent.leftnode.parent.left=nullnode == node.parent.rightnode.parent.right=nullnode.parent == nullroot = null

2.2.2 删除节点-度为1的节点

// 用子节点替代原节点的位置child是node.left或者child是node.right// 用child替代node的位置// 如果node是左子节点child.parent = node.parentnode.parent.left = child// 如果node是右子节点child.parent = node.parentnode.parent.right = child// 如果node是根结点root = childchild.parent = null

2.2.3 删除节点-度为2的节点

• 先用前驱或者后继节点的值覆盖原节点的值
• 然后删除相应的前驱或者后继节点
• 如果一个节点的度为2，那么它的前驱、后继节点的度只可能是1和0.

// 删除元素	public void remove(E element) {
   		remove(node(element));	}	private void remove(Node
   
     node) {
   		if(node==null)			return;		size--;				// 度为2的结点		if(node.hasTwoChildren()) {
   			// 找到后继结点			Node
    
      s = successor(node);			node.element = s.element;			node = s;		}				// 删除node结点，node结点必然是度为0或者度为1		Node
     
       replacement = node.left!=null?node.left:node.right;		if(replacement!=null) {
   			// node的度为1的结点			replacement.parent = node.parent;			// 更改指向			if(node.parent==null) {
   				// node是度为1的结点并且是根节点				root = replacement;			}else if(node==node.parent.left) {
   				node.parent.left = replacement;			}else {
   				node.parent.right = replacement;			}		}else if(node.parent==null) {
   			// node是叶子结点并且是叶子结点			root = null;		}else {
   			// node是叶子结点，但不是根节点			if(node==node.parent.left) {
   				node.parent.left = null;			}else {
   				node.parent.right = null;			}		}			}		// 后继结点		protected Node
      
        successor(Node
       
         node){
   			if(node==null)				return null;			// 后继结点在右子树			Node
        
          p = node.right; if(p!=null) { while(p.left!=null) { p = p.left; } return p; } // 从父节点、祖父结点寻找后继结点 while(node.parent!=null&&node==node.parent.right) { node = node.parent; } return node.parent; }
        
       
      
     
    
   

2.2.4 二叉搜索树删除某个节点的递归

// 后继	private int successor(TreeNode root) {
   		root = root.right;		while(root.left!=null) {
   			root = root.left;		}		return root.val;	}		// 前驱	private int predecessor(TreeNode root) {
   		root = root.left;		while(root.left!=null) {
   			root = root.right;		}		return root.val;	}	public TreeNode deleteNode(TreeNode root,int key) {
   		// 递归结束条件		if(root==null)			return null;		// 判断条件		if(key>root.val)			root.right = deleteNode(root.right, key);		else if(key

2.3 二叉搜索迭代器

package com.lcz.leetcode;/** * 二叉搜索树 * @author LvChaoZhang * */import java.util.*;public class Leetcode173 {
   	class TreeNode{
   		int val;		TreeNode left;		TreeNode right;		TreeNode(int x){
   			val = x;		}	}		class BSTIterator {
   	    int index;	    ArrayList
   
     list;	    public BSTIterator(TreeNode root) {
   	        this.list = new ArrayList<>();	        this.index = -1;	        this.inorder(root);	    }	    // 先进行中序遍历	    private void inorder(TreeNode root){
   	        if(root==null){
   	            return;	        }	        inorder(root.left);	        list.add(root.val);	        inorder(root.right);	    }	    	    /** @return the next smallest number */	    public int next() {
   	        return list.get(++index);	    }	    	    /** @return whether we have a next smallest number */	    public boolean hasNext() {
   	        return this.index+1 < this.list.size();	    }	}
   

class BSTIterator {
   	    // 栈	    Stack
   
     stack;	    public BSTIterator(TreeNode root) {
   	        // 初始化	        stack = new Stack<>();	        this.pre(root);	    }	    // 先存储一部分值	    private void pre(TreeNode root){
   	        while(root!=null){
   	            stack.push(root);	            root = root.left;	        }	    }	    /** @return the next smallest number */	    public int next() {
   	        TreeNode temp = this.stack.pop();	        if(temp.right!=null){
   	            this.pre(temp.right);	        }	        return temp.val;	    }	    	    /** @return whether we have a next smallest number */	    public boolean hasNext() {
   	        return this.stack.size()>0;	    }	}	/**	 * Your BSTIterator object will be instantiated and called as such:	 * BSTIterator obj = new BSTIterator(root);	 * int param_1 = obj.next();	 * boolean param_2 = obj.hasNext();	 */}
   

2.4 恢复二叉搜索树

// 二叉搜索树的隐式恢复	public void recoverTree_2(TreeNode root) {
   		Stack
   
     stack = new Stack<>();		TreeNode x = null, y = null, pred= null;		while(!stack.isEmpty()||root!=null) {
   			while(root!=null) {
   				stack.push(root);				root = root.left;			}			root = stack.pop();			if(pred!=null&&root.val
   

四、平衡二叉树(Balance Binary Search Tree)

1. 二叉搜索树的复杂度分析

退化成链表的一种情况

2. 平衡(Balance)

理想平衡

3. 如何改进二叉搜索树

4. 平衡二叉搜索树（Balanced Binary Search Tree）

• 英文简称为：BBST

• 经典常见的平衡二叉搜索树有

  • AVL树
    • Windows NT内核中广泛使用
  • 红黑树
    • C++ STL（比如map、set）
    • Java的TreeMap、TreeSet、HashMap、HashSet
    • Linux的进程调度
    • Nginx的timer管理

• 一般也称为：自平衡的二叉搜索树(Self-balancing Binary Search Tree)

五、AVL树

• AVL树是最早发明的自平衡二叉搜索树之一

• AVL取名于两位发明者的名字

• G.M.Adelson-Velsky和E.M.Landis

• 平衡因子（Balanced Factor）:某结点的左右子树的高度差

• AVL树的特点：

  • 每个节点的平衡因子只可能是1,0,-1
  • 每个节点的左右子树高度差不超过1
  • 搜索、添加、删除的时间复杂度是O(logn)

1. 简单的继承结构

2. 添加导致的失衡

• 示例：往下面这棵子树中添加13
• 最坏情况：可能会导致所有祖先节点都失衡
• 父节点、非祖先节点，都不可能失衡

3. 失衡的几种情况以及解决措施

3.1 LL-右旋转

• g.left = p.right
• p.right = g
• 让p成为这课子树的根结点
• T2,p,g的parent属性更新
• 先后更新g,p的高度

3.2 RR-左旋转

• g.right= p.left
• p.left= g
• 让p成为这课子树的根结点
• T2,p,g的parent属性更新
• 先后更新g,p的高度

3.3 LR-RR左旋转，LL右旋转

3.4 RL-LL右旋转，RR左旋转

4. 添加节点之后的修复代码

4.1 AVLNode类节点

• height高度属性
• 更新节点高度功能
• 计算节点的平衡因子
• 查找该节点的左右节点哪个更高

// AVL结点	private static class AVLNode
   
     extends Node
    
     {
   		int height = 1;		public AVLNode(E element, Node
     
       parent) {
   			super(element, parent);			// TODO Auto-generated constructor stub		}				// 计算平衡因子		public int balanceFacotr() {
   			int leftHeight = left==null?0:((AVLNode
      
       )left).height;			int rightHeight = right==null?0:((AVLNode
       
        )right).height;			return leftHeight-rightHeight;		}						// 更新结点的高度		public void updateHeight() {
   			int leftHeight = left==null?0:((AVLNode
        
         )left).height; int rightHeight = right==null?0:((AVLNode
         
          )right).height; height = 1+ Math.max(leftHeight,rightHeight); } // 查找该结点的左右结点哪个更高 public Node
          
            tallerChild(){ int leftHeight = left==null?0:((AVLNode
           
            )left).height; int rightHeight = right==null?0:((AVLNode
            
             )right).height; if(leftHeight>rightHeight) return left; if(leftHeight
            
           
          
         
        
       
      
     
    
   

4.2 添加节点之后的修复

// 添加结点之后重新平衡	@Override	protected void afterAdd(Node
   
     node) {
   		while((node=node.parent)!=null) {
   			if(isBalanced(node)) {
   				// 更新高度				updateHeight(node);			}else {
   				// 恢复平衡				rebanlce(node);				break;			}		}	}
   

// 判断结点是否平衡	private boolean isBalanced(Node
   
     node) {
   		return Math.abs(((AVLNode
    
     )node).balanceFacotr())<=1;	}		// 更新结点高度	private void updateHeight(Node
     
       node) {
   		((AVLNode
      
       )node).updateHeight();	}		// 恢复平衡	private void rebanlce(Node
       
         grand) {
   		Node
        
          parent = ((AVLNode
         
          )grand).tallerChild(); Node
          
            node = ((AVLNode
           
            )parent).tallerChild(); if(parent.isLeftChild()) { //L if(node.isLeftChild()) { //L rotateRight(grand); // LL }else { //LR rotateLeft(parent); rotateRight(grand); } }else { //R if(node.isLeftChild()) { //RL rotateRight(parent); rotateLeft(grand); }else { // RR rotateLeft(grand); } } }
           
          
         
        
       
      
     
    
   

// 左旋转	private void rotateLeft(Node
   
     grand) {
   		Node
    
      parent = grand.right;		Node
     
       child = parent.left;		grand.right = child;		parent.left = grand;		//更新其父节点以及高度		afterRotate(grand,parent,child);	}		// 右旋转	private void rotateRight(Node
      
        grand) {
   		Node
       
         parent = grand.left;		Node
        
          child = parent.right; grand.left = child; parent.right = grand; // 更新其父节点以及高度 afterRotate(grand, parent, child); } //更新其父节点以及高度 private void afterRotate(Node
         
           grand,Node
          
            parent,Node
           
             child) { // 更新parent结点 parent.parent = grand.parent; if(grand.isLeftChild()) { grand.parent.left = parent; }else if(grand.isRightChild()) { grand.parent.right = parent; }else { root = parent; } // 更新child if(child!=null) { child.parent = grand; } // 更新grand grand.parent = parent; // 更新高度 updateHeight(grand); updateHeight(parent); }
           
          
         
        
       
      
     
    
   

效果图：

4.3 统一所有旋转操作

对所有节点进行标记a-g，然后对其调整。观察a-g。

4.4 删除导致的失衡

4.5 删除之后的修复代码

// 删除节点之后重新平衡	protected void afterRemove(Node
   
     node) {
   		while((node=node.parent)!=null) {
   			if(isBalanced(node)) {
   				// 更新高度				updateHeight(node);			}else {
   				// 恢复平衡				rebanlce(node);			}		}	}
   

4.6 总结

• 添加
  • 可能会导致所有祖先节点都失衡
  • 只要让高度最低的失衡节点恢复平衡，整棵树就恢复平衡
• 删除
  • 可能导致父节点或祖先节点失衡
  • 恢复平衡后可能会导致更高层的祖先节点失衡
• 平均时间复杂度
  • 搜索 O(logn)
  • 添加 O(logn) 仅需O(1)次旋转操作
  • 删除O(logn) 最多需要O(logn)次的旋转操作

六、B树

1. m阶B树的性质(m>=2)

2 添加节点

3. 添加节点-上溢的解决

4. 删除节点

4.1 删除节点-叶子节点

4.2 删除节点-非叶子节点

5. 删除-下溢

6. 4阶B树

• 4阶B树的性质
  • 所有节点能存储的元素个数x：1<=x<=3
  • 所有非叶子节点的子节点个数y:2<=y<=4

七、红黑树(Red Black Tree)

红黑树必须满足以下5条性质：

• 1.节点必须是RED或者BLACK

• 2.根结点是BLACK

• 3.叶节点(外部节点、空节点)都是BLACK

• 4.RED节点的子节点都是BLACK

  RED节点的parent都是BLACK

  从根结点到叶子节点的所有路径上不能有2个连续的RED节点

• 5.从任一节点到叶子节点的所有路径都包含相同数目的BLACK节点

1. 红黑树的等价替换

• 红黑树和4阶B树具有等价性
• BLACK节点与它的RED子节点融合在一起，形成1个B树节点
• 红黑树的BLACK节点个数与4阶B树的节点总个数 相等

2. 添加节点

• B树中，新元素必定是添加到叶子节点中
• 4阶B树中所有节点的元素个数x都符合1<=x<=3
• 建议新添加的节点默认为RED,这样能够让红黑树的性质尽快满足(性质1,2,3,5,都满足，性质4不一定满足)

public class RBTree
   
     extends BalanceBinarySearchTree
    
      {
   	public RBTree() {
   		this(null);	}	public RBTree(Comparator
     
       comparator) {
   		super(comparator);	}		// 两个常量	private static final boolean RED = false;	private static final boolean BLACK = false;		/**	 * 一些功能函数	 */	// 染色	private Node
      
        color(Node
       
         node,boolean color){
   		if(node==null)			return node;		((RBNode
        
         )node).color = color; return node; } // 染成红色 private Node
         
           red(Node
          
            node){ return color(node,RED); } // 染成黑色 private Node
           
             black(Node
            
              node){ return color(node,BLACK); } // 判断其颜色 private boolean colorOf(Node
             
               node) { return node==null?BLACK:((RBNode
              
               )node).color; } // 判断是否为黑色 private boolean isBlack(Node
               
                 node) { return colorOf(node)==BLACK; } // 判断是否为红色 private boolean isRed(Node
                
                  node) { return colorOf(node)==RED; } protected Node
                 
                   createNode(E element,Node
                  
                    parent){ return new RBNode<>(element,parent); } // 红黑树的结点 private static class RBNode
                   
                     extends Node
                    
                     { boolean color = RED; public RBNode(E element,Node
                     
                       parent) { super(element,parent); } @Override public String toString() { String str = ""; if(color==RED) { str="R_"; } return str+element.toString(); } } }
                     
                    
                   
                  
                 
                
               
              
             
            
           
          
         
        
       
      
     
    
   

2.1添加的所有情况

红黑树的添加共用12种情况。

• 其中有4种情况满足红黑树的性质4：parent为BLACK

  

• 其中有8种情况不满足红黑树的性质4：parent为RED(double red)

2.3 添加-修复性质4-LL\RR

• 判定条件：uncle不是RED
  • 1.parent染成BLACK，grand染成RED
  • 2.grand进行单旋操作
    • LL：右旋转
    • RR：左旋转

2.4 添加-修复性质4-LR\RL

• 判定条件：uncle不是RED
  • 1.自己染成BLACK，grand染成RED
  • 2.进行双旋操作
    • LR:parent左旋转 grand右旋转
    • RL:parent右旋转，grand左旋转

2.5 添加-修复性质4-上溢LL

• 判定条件：uncle是RED
  • 1.parent、uncle染成black
  • 2.grand向上合并
    • 染成RED，当做是新添加的节点进行处理，grand向上合并，可能会继续发生上溢，若上溢到根结点，只需将根结点染成BLACK

2.6 添加-修复性质4-上溢RR

• 判定条件：uncle是RED
  • 1.parent、uncle染成black
  • 2.grand向上合并
    • 染成RED，当做是新添加的节点进行处理

2.7 添加-修复性质4-上溢LR

• 判定条件：uncle是RED
  • 1.parent、uncle染成black
  • 2.grand向上合并
    • 染成RED，当做是新添加的节点进行处理

2.8 添加-修复性质4-上溢RL

• 判定条件：uncle是RED
  • 1.parent、uncle染成black
  • 2.grand向上合并
    • 染成RED，当做是新添加的节点进行处理

3. 添加节点-处理代码

// 添加之后的操作	@Override	protected void afterAdd(Node
   
     node) {
   		Node
    
      parent = node.parent;		// 添加的根节点或者上溢到了根节点		if(parent==null) {
   			black(node);			return;		}				// 4种情况		// 父节点为黑色结点 直接添加返回		if(isBlack(parent))			return;				// 8种情况		// 叔父结点		Node
     
       uncle = parent.sibling();		// 祖父结点		Node
      
        grand = parent.parent;		// 4种情况		if(isRed(uncle)) {
   			black(parent);			black(uncle);			//祖父结点			red(grand);			afterAdd(grand);			return;		}				//4种情况		if(parent.isLeftChild()) {
   //L			if(node.isLeftChild()) {
   				//LL				red(grand);				black(parent);				rotateRight(grand);			}else {
   				//LR				red(grand);				black(node);				rotateLeft(parent);				rotateRight(grand);			}		}else {
   			if(node.isLeftChild()) {
   				//RL				red(grand);				black(node);				rotateRight(parent);
      
     
    
   

4. 删除节点

B树中，最后真正被删除的元素都在叶子节点中。

4.1 删除的所有情况

• 删除-RED节点(直接删除，不用作任何调整)
• 删除-BLACK节点
  • 拥有两个RED子节点的BLACK节点
  • 拥有1个RED子节点的BLACK节点
  • BLACK叶子节点

4.2 删除的代码

@Override	protected void afterRemove(Node
   
     node) {
   		// 如果删除的节点是红色		// 或者 用以取代删除节点的子节点是红色		if (isRed(node)) {
   			black(node);			return;		}				Node
    
      parent = node.parent;		// 删除的是根节点		if (parent == null) return;				// 删除的是黑色叶子节点【下溢】		// 判断被删除的node是左还是右		boolean left = parent.left == null || node.isLeftChild();		Node
     
       sibling = left ? parent.right : parent.left;		if (left) {
    // 被删除的节点在左边，兄弟节点在右边			if (isRed(sibling)) {
    // 兄弟节点是红色				black(sibling);				red(parent);				rotateLeft(parent);				// 更换兄弟				sibling = parent.right;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {
   				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {
   					afterRemove(parent);				}			} else {
    // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.right)) {
   					rotateRight(sibling);					sibling = parent.right;				}								color(sibling, colorOf(parent));				black(sibling.right);				black(parent);				rotateLeft(parent);			}		} else {
    // 被删除的节点在右边，兄弟节点在左边			if (isRed(sibling)) {
    // 兄弟节点是红色				black(sibling);				red(parent);				rotateRight(parent);				// 更换兄弟				sibling = parent.left;			}						// 兄弟节点必然是黑色			if (isBlack(sibling.left) && isBlack(sibling.right)) {
   				// 兄弟节点没有1个红色子节点，父节点要向下跟兄弟节点合并				boolean parentBlack = isBlack(parent);				black(parent);				red(sibling);				if (parentBlack) {
   					afterRemove(parent);				}			} else {
    // 兄弟节点至少有1个红色子节点，向兄弟节点借元素				// 兄弟节点的左边是黑色，兄弟要先旋转				if (isBlack(sibling.left)) {
   					rotateLeft(sibling);					sibling = parent.left;				}								color(sibling, colorOf(parent));				black(sibling.left);				black(parent);				rotateRight(parent);			}		}	}
     
    
   

5. 红黑树的平衡

• 为什么红黑树那5条性质，就能保证红黑树是平衡的？
• 相比较AVL树，红黑树的平衡标准比较宽松：没有一条路径会大于其他路径的2倍
• 是一种弱平衡、黑高度平衡。

6. AVL树 VS 红黑树

◼ AVL树

• 平衡标准比较严格：每个左右子树的高度差不超过1
• 最大高度是 1.44 ∗ log2 n + 2 − 1.328（100W个节点，AVL树最大树高28）
• 搜索、添加、删除都是 O(logn) 复杂度，其中添加仅需 O(1) 次旋转调整、删除最多需要 O(logn) 次旋转调整

◼ 红黑树

• 平衡标准比较宽松：没有一条路径会大于其他路径的2倍
• 最大高度是 2 ∗ log2(n + 1)（ 100W个节点，红黑树最大树高40）
• 搜索、添加、删除都是 O(logn) 复杂度，其中添加、删除都仅需 O(1) 次旋转调整

◼ 搜索的次数远远大于插入和删除，选择AVL树；搜索、插入、删除次数几乎差不多，选择红黑树

◼ 相对于AVL树来说，红黑树牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树

◼ 红黑树的平均统计性能优于AVL树，实际应用中更多选择使用红黑树

八、二叉堆

1. 二叉堆

二叉堆的逻辑结构就是一颗完全二叉树，所以也叫完全二叉堆。

2. 重要接口设计

2.1 二叉堆-添加操作

在最后面添加元素，并上滤。

2.2 二叉堆-删除操作

2.3 二叉堆-替换操作

/**	 * 删除元素并替换	 */	@Override	public E replace(E element) {
   		elementNotNullCheck(element);				E root = null;		if(size==0) {
   			elements[0] = element;			size++;		}else {
   			root = elements[0];			elements[0] = element;			siftDown(0);		}				return root;	}

2.4 二叉堆-批量建堆

• 批量建堆，有2种方法
  • 自上而下的上滤
  • 自下而上的下滤

2.4.1 二叉堆-批量建堆-自上而下的上滤

2.4.2 二叉堆-批量建堆-自下而上的下滤

2.4.3 二叉堆-批量建堆-效率比较

3. 源码

package com.mj.heap;import java.util.Comparator;import com.mj.printer.BinaryTreeInfo;/** * 二叉堆（最大堆） * @author MJ Lee * * @param 
   
     */@SuppressWarnings("unchecked")public class BinaryHeap
    
      extends AbstractHeap
     
       implements BinaryTreeInfo {
   	private E[] elements;	private static final int DEFAULT_CAPACITY = 10;		public BinaryHeap(E[] elements, Comparator
      
        comparator)  {
   		super(comparator);				if (elements == null || elements.length == 0) {
   			this.elements = (E[]) new Object[DEFAULT_CAPACITY];		} else {
   			size = elements.length;			int capacity = Math.max(elements.length, DEFAULT_CAPACITY);			this.elements = (E[]) new Object[capacity];			for (int i = 0; i < elements.length; i++) {
   				this.elements[i] = elements[i];			}			heapify();		}	}		public BinaryHeap(E[] elements)  {
   		this(elements, null);	}		public BinaryHeap(Comparator
       
         comparator) {
   		this(null, comparator);	}		public BinaryHeap() {
   		this(null, null);	}	@Override	public void clear() {
   		for (int i = 0; i < size; i++) {
   			elements[i] = null;		}		size = 0;	}	@Override	public void add(E element) {
   		elementNotNullCheck(element);		ensureCapacity(size + 1);		elements[size++] = element;		siftUp(size - 1);	}	@Override	public E get() {
   		emptyCheck();		return elements[0];	}	@Override	public E remove() {
   		emptyCheck();				int lastIndex = --size;		E root = elements[0];		elements[0] = elements[lastIndex];		elements[lastIndex] = null;				siftDown(0);		return root;	}	@Override	public E replace(E element) {
   		elementNotNullCheck(element);				E root = null;		if (size == 0) {
   			elements[0] = element;			size++;		} else {
   			root = elements[0];			elements[0] = element;			siftDown(0);		}		return root;	}		/**	 * 批量建堆	 */	private void heapify() {
   		// 自上而下的上滤//		for (int i = 1; i < size; i++) {
   //			siftUp(i);//		}				// 自下而上的下滤		for (int i = (size >> 1) - 1; i >= 0; i--) {
   			siftDown(i);		}	}		/**	 * 让index位置的元素下滤	 * @param index	 */	private void siftDown(int index) {
   		E element = elements[index];		int half = size >> 1;		// 第一个叶子节点的索引 == 非叶子节点的数量		// index < 第一个叶子节点的索引		// 必须保证index位置是非叶子节点		while (index < half) {
    			// index的节点有2种情况			// 1.只有左子节点			// 2.同时有左右子节点						// 默认为左子节点跟它进行比较			int childIndex = (index << 1) + 1;			E child = elements[childIndex];						// 右子节点			int rightIndex = childIndex + 1;						// 选出左右子节点最大的那个			if (rightIndex < size && compare(elements[rightIndex], child) > 0) {
   				child = elements[childIndex = rightIndex];			}						if (compare(element, child) >= 0) break;			// 将子节点存放到index位置			elements[index] = child;			// 重新设置index			index = childIndex;		}		elements[index] = element;	}		/**	 * 让index位置的元素上滤	 * @param index	 */	private void siftUp(int index) {
   //		E e = elements[index];//		while (index > 0) {
   //			int pindex = (index - 1) >> 1;//			E p = elements[pindex];//			if (compare(e, p) <= 0) return;//			//			// 交换index、pindex位置的内容//			E tmp = elements[index];//			elements[index] = elements[pindex];//			elements[pindex] = tmp;//			//			// 重新赋值index//			index = pindex;//		}		E element = elements[index];		while (index > 0) {
   			int parentIndex = (index - 1) >> 1;			E parent = elements[parentIndex];			if (compare(element, parent) <= 0) break;						// 将父元素存储在index位置			elements[index] = parent;						// 重新赋值index			index = parentIndex;		}		elements[index] = element;	}		private void ensureCapacity(int capacity) {
   		int oldCapacity = elements.length;		if (oldCapacity >= capacity) return;				// 新容量为旧容量的1.5倍		int newCapacity = oldCapacity + (oldCapacity >> 1);		E[] newElements = (E[]) new Object[newCapacity];		for (int i = 0; i < size; i++) {
   			newElements[i] = elements[i];		}		elements = newElements;	}		private void emptyCheck() {
   		if (size == 0) {
   			throw new IndexOutOfBoundsException("Heap is empty");		}	}		private void elementNotNullCheck(E element) {
   		if (element == null) {
   			throw new IllegalArgumentException("element must not be null");		}	}	@Override	public Object root() {
   		return 0;	}	@Override	public Object left(Object node) {
   		int index = ((int)node << 1) + 1;		return index >= size ? null : index;	}	@Override	public Object right(Object node) {
   		int index = ((int)node << 1) + 2;		return index >= size ? null : index;	}	@Override	public Object string(Object node) {
   		return elements[(int)node];	}}
       
      
     
    
   

4. Top K 问题

• 从n个整数中，找出最大的前K个数(k远远小于n)

• 如果使用排序算法进行全排序，需要O(nlogn)的时间复杂度

• 如果使用二叉堆来解决，可以使用O(nlogk)的时间复杂度来解决

  • 新建一个小顶堆
  • 扫描n个数
    • 先将遍历到的前K个数放入堆中
    • 从第K+1个数开始，如果大于堆顶元素，就使用replace操作(删除栈顶元素，将第k+1个数添加到堆中)
  • 扫描完毕后，堆中剩下的就是最大的前k个最大数

• 如果是找出最小的前k个数呢？

  • 用大顶堆
  • 如果小于堆顶元素，就使用replace操作。

九、优先级队列

1. 优先级队列(Priority Queue)

• int size(); //元素的数量
• boolean isEmpty(); //是否为空
• void enQueue(E element); //入队
• E deQueue(); //出队
• E front(); //获取队列的头元素
• void clear(); //清空

普通的队列是FIFO原则，也就是先进先出

优先级队列是按照优先级高低进行出队，比如将优先级最高的元素作为对头优先出队。

2. 优先级队列接口实现

public class PriorityQueue
   
     {
   	private BinaryHeap
    
      heap;		public PriorityQueue(Comparator
     
       comparator) {
   		heap = new BinaryHeap<>(comparator);	}		public PriorityQueue() {
   		this(null);	}		public int size() {
   		return heap.size();	}	public boolean isEmpty() {
   		return heap.isEmpty();	}		public void clear() {
   		heap.clear();	}	public void enQueue(E element) {
   		heap.add(element);	}	public E deQueue() {
   		return heap.remove();	}	public E front() {
   		return heap.get();	}}
     
    
   

Java中的PriorityQueue

PriorityQueue
   
     queue =  new PriorityQueue
    
     ();		queue.offer(new Person("Jack",2));		queue.offer(new Person("Rose",10));		queue.offer(new Person("Jake",1));				while(!queue.isEmpty()) {
   			System.out.println(queue.poll());		}
    
   

3. 优先级队列的应用场景举例

• 医院的夜间门诊
  • 队列元素是病人
  • 优先级是病情的严重情况、挂号时间
• 操作系统的多任务调度
  • 队列元素是任务
  • 优先级是

十、哈夫曼树

1. 哈夫曼编码(Huffman Coding)

• 哈夫曼编码，又称为霍夫曼编码，它是现代压缩算法的基础
  

2. 哈夫曼树

2.1 构建哈夫曼树

2.2 构建哈夫曼编码

十一、Trie

1. 需求

• 如何判断一堆不重复的字符串是否以某个前缀开头？
  • 用Set/Map存储字符串
  • 遍历所有字符串进行判断
  • 时间复杂度
  • O（n）

2. Trie

• Trie也叫作字典树、前缀树、单词查找树
• Trie搜索字符串的效率主要跟字符串的长度有关
• 假设使用Trie存储cat、dog、doggy、does、cast、add六个单词

3. 接口设计

• int size();
• boolean isEmpty();
• void clear();
• boolean contains(String str);
• V add(String str,V value);
• V remove(String str);
• boolean starsWith(String prefix);

public class Trie
   
     {
   	private int size;	private Node
    
      root;		public int size() {
   		return size;	}	public boolean isEmpty() {
   		return size == 0;	}	public void clear() {
   		size = 0;		root = null;	}	public V get(String key) {
   		Node
     
       node = node(key);		return node != null && node.word ? node.value : null;	}	public boolean contains(String key) {
   		Node
      
        node = node(key);		return node != null && node.word;	}	public V add(String key, V value) {
   		keyCheck(key);				// 创建根节点		if (root == null) {
   			root = new Node<>(null);		}		Node
       
         node = root;		int len = key.length();		for (int i = 0; i < len; i++) {
   			char c = key.charAt(i); 			boolean emptyChildren = node.children == null;			Node
        
          childNode = emptyChildren ? null : node.children.get(c); if (childNode == null) { childNode = new Node<>(node); childNode.character = c; node.children = emptyChildren ? new HashMap<>() : node.children; node.children.put(c, childNode); } node = childNode; } if (node.word) { // 已经存在这个单词 V oldValue = node.value; node.value = value; return oldValue; } // 新增一个单词 node.word = true; node.value = value; size++; return null; } public V remove(String key) { // 找到最后一个节点 Node
         
           node = node(key); // 如果不是单词结尾，不用作任何处理 if (node == null || !node.word) return null; size--; V oldValue = node.value; // 如果还有子节点 if (node.children != null && !node.children.isEmpty()) { node.word = false; node.value = null; return oldValue; } // 如果没有子节点 Node
          
            parent = null; while ((parent = node.parent) != null) { parent.children.remove(node.character); if (parent.word || !parent.children.isEmpty()) break; node = parent; } return oldValue; } public boolean startsWith(String prefix) { return node(prefix) != null; } private Node
           
             node(String key) { keyCheck(key); Node
            
              node = root; int len = key.length(); for (int i = 0; i < len; i++) { if (node == null || node.children == null || node.children.isEmpty()) return null; char c = key.charAt(i); node = node.children.get(c); } return node; } private void keyCheck(String key) { if (key == null || key.length() == 0) { throw new IllegalArgumentException("key must not be empty"); } } private static class Node
             
               { Node
              
                parent; HashMap
               
                > children; Character character; V value; boolean word; // 是否为单词的结尾（是否为一个完整的单词） public Node(Node
                
                  parent) { this.parent = parent; } }}
                
               
              
             
            
           
          
         
        
       
      
     
    
   

4. 总结

• Trie的优点：搜索前缀的效率主要跟前缀的长度有关

• Trie的缺点：需要耗费大量的内存，因此还有待改进

  Node
       
         node = node(key);  return node != null && node.word;
       

  }

  public V add(String key, V value) {

  keyCheck(key);

  // 创建根节点  if (root == null) {  	root = new Node<>(null);  }  Node
       
         node = root;  int len = key.length();  for (int i = 0; i < len; i++) {  	char c = key.charAt(i);   	boolean emptyChildren = node.children == null;  	Node
        
          childNode = emptyChildren ? null : node.children.get(c);  	if (childNode == null) {  		childNode = new Node<>(node);  		childNode.character = c;  		node.children = emptyChildren ? new HashMap<>() : node.children;  		node.children.put(c, childNode);  	}  	node = childNode;  }    if (node.word) { // 已经存在这个单词  	V oldValue = node.value;  	node.value = value;  	return oldValue;  }    // 新增一个单词  node.word = true;  node.value = value;  size++;  return null;
        
       

  }

  public V remove(String key) {

  // 找到最后一个节点
  Node node = node(key);
  // 如果不是单词结尾，不用作任何处理
  if (node == null || !node.word) return null;
  size–;
  V oldValue = node.value;

  // 如果还有子节点  if (node.children != null && !node.children.isEmpty()) {  	node.word = false;  	node.value = null;  	return oldValue;  }    // 如果没有子节点  Node
       
         parent = null;  while ((parent = node.parent) != null) {  	parent.children.remove(node.character);  	if (parent.word || !parent.children.isEmpty()) break;  	node = parent;  }    return oldValue;
       

  }

  public boolean startsWith(String prefix) {

  return node(prefix) != null;
  }

  private Node node(String key) {

  keyCheck(key);

  Node
       
         node = root;  int len = key.length();  for (int i = 0; i < len; i++) {  	if (node == null || node.children == null || node.children.isEmpty()) return null;  	char c = key.charAt(i);   	node = node.children.get(c);  }    return node;
       

  }

  private void keyCheck(String key) {

  if (key == null || key.length() == 0) {
  throw new IllegalArgumentException(“key must not be empty”);
  }
  }

  private static class Node {

  Node parent;
  HashMap<Character, Node> children;
  Character character;
  V value;
  boolean word; // 是否为单词的结尾（是否为一个完整的单词）
  public Node(Node parent) {
  this.parent = parent;
  }
  }
  }

## 4. 总结- Trie的优点：搜索前缀的效率主要跟前缀的长度有关- Trie的缺点：需要耗费大量的内存，因此还有待改进![在这里插入图片描述](https://img-blog.csdnimg.cn/2020111113110693.gif#pic_center)

转载地址：https://codingchaozhang.blog.csdn.net/article/details/109616665 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！