分类

  • 二分搜索树(Binary Search Tree)
  • 红黑树、AVL
  • 字典树、前缀树

构建二叉树

  1. private class Node{
  2.     public E e;
  3.     public Node left;
  4.     public Node right;
  5.     public Node(E e){
  6.         this.e = e;
  7.         left = null;
  8.         right = null;
  9.     }
  10. }

二分搜索树

二分搜索树是二叉树，二分搜索树的每个节点的值满足

  1. 大于其左子树的所有结点的值
  2. 小于其右子树的所有结点的值
  3. 每个子树也是一个二分搜索树

特点：每个节点的key值大于左节点 小于右节点

结论：

  • 二叉搜索树的最小节点是根节点左边子树的最左子树
  • 二叉搜索树的最大节点是根节点右边子树的最右子树

插入操作

二分搜索树 - 图1

  1. public void add(E e){
  2.     if(root == null){
  3.         root = new Node(e);
  4.         size++;
  5.     }else
  6.         add(root, e);
  7. }
  9. //向以node为根的二分搜索树中插入元素E
  10. private void add(Node node, E e){
  11.     if(e.equals(node.e)){ //终止条件
  12.         return;
  13.     }else if(e.compareTo(node.e) <0 && node.left == null){
  14.         node.left = new Node(e);
  15.         size++;
  16.         return ;
  17.     }else if(e.compareTo(node.e) >0 && node.right == null){
  18.         node.right = new Node(e);
  19.         size++;
  20.         return;
  21.     }
  23.     if(e.compareTo(node.e) < 0)
  24.         add(node.left, e);
  25.     else
  26.         add(node.right, e);
  27. }

简化版

  1. //添加元素
  2. public void add(E e){
  3.     root = add(root, e);
  4. }
  5. //向以node为根的二分搜索树中插入元素E
  6. private Node add(Node node, E e){
  7.     if(node == null){
  8.         size++;
  9.         return new Node(e);
  10.     }
  11.     //比较插入的元素与node节点的大小
  12.     if(e.compareTo(node.e) < 0){
  13.         node.left = add(node.left,e);// 
  14.     }else if(e.compareTo(node.e)>0){
  15.         node.right = add(node.right,e);
  16.     }
  17.     return node;
  18. }

查询元素

  1. /*查询元素*/
  2. public boolean contains(E e){
  3.     return contains(root, e);
  4. }
  5. private boolean contains(Node node, E e){
  6.     if(node == null)//终止条件
  7.         return false;
  8.     if(e.compareTo(node.e) == 0)
  9.         return true; //找到了
  10.     else if(e.compareTo(node.e) <0)
  11.         return contains(node.left, e);
  12.     else
  13.         return contains(node.right, e);
  14. }

遍历操作

  • 前序遍历（根、左、右）
  • 中序遍历（左、根、右）
  • 后序遍历（左、右、根）
  1. /*前序遍历*/
  2. public void preOrder(){
  3.     preOrder(root);
  4. }
  5. private void preOrder(Node node){
  6.     if(node == null)
  7.         return;
  8.     System.out.println(node.e);
  9.     preOrder(node.left);//访问左
  10.     preOrder(node.right);//访问右
  11. }
  1. /*中序遍历*/
  2. public void midOrder(){
  3.     midOrder(root);
  4. }
  5. public void midOrder(Node node){
  6.     if(node == null)
  7.         return;
  8.     midOrder(node.left);
  9.     System.out.println(node.e);
  10.     midOrder(node.right);
  11. }

惊奇的是这样的树经过中序遍历后元素是经过排过序的

  1. /*后序遍历*/
  2. public void postOrder(){
  3.     postOrder(root);
  4. }
  5. private void postOrder(Node node){
  6.     if(node == null)
  7.         return;
  8.     postOrder(node.left);
  9.     postOrder(node.right);
  10.     System.out.println(node.e);
  11. }

二分搜索树的层序遍历

也是对树的bfs

  1. public void bfs(){
  2.     //借助队列的数据结构
  3.     Queue<Node> q = new ArrayDeque<>();
  4.     //首先添加root结点
  5.     q.add(root);
  7.     while(!q.isEmpty()){
  8.         Node cur = q.remove();
  9.         System.out.print(cur.e);
  11.         if(cur.left != null) //添加左孩子与右孩子
  12.             q.add(cur.left);
  13.         if(cur.right != null)
  14.             q.add(cur.right);
  15.     }
  16. }

删除操作

首先确立二分搜索树的最大值与最小值

最小值一定会在根元素左的最左边。如果最小值拥有右子树，删除本节点右子树代替当前位置

最大值一定会在根元素的右的最右边。如果是一个叶子节点直接删除如果拥有左子树，则删除本节点 本节点的左子树代替当前位置。

先看一下如何查找元素

二分搜索树 - 图2

  1. /*寻找最大值与最小值*/
  2. public E findMax(){
  3.     if(size==0)
  4.         throw new IllegalArgumentException("Is Empty!");
  5.     return findMax(root).e;
  6. }
  7. private Node findMax(Node node){
  8.     if(node.right == null)
  9.         return node;
  10.     return findMax(node.right);
  11. }
  12. public E findMin(){
  13.     if(size==0)
  14.         throw new IllegalArgumentException("Is Empty!");
  15.     return findMin(root).e;
  16. }
  17. private Node findMin(Node node){
  18.     if(node.left == null)
  19.         return node;
  20.     return findMin(node.left);
  21. }
  22. // 删除最大值与最小值
  23. //删除以node为根的二分搜索树中的最大节点 返回删除节点后新的二分搜索树的根
  24. public E removeMax(){
  25.     E res = findMax();
  26.     root = removeMax(root);
  27.     return res;
  28. }
  29. private Node removeMax(Node node){ //传入结点
  30.     if(node.right == null){//已经递归到底
  31.         Node leftNode = node.left; //接住结点的左树
  32.         node.left = null;
  33.         size--;
  34.         return leftNode;
  35.     }
  36.     node.right = removeMax(node.right);
  37.     return node;
  38. }

删除单个节点的分类

  1. 拥有一个左子树
  2. 拥有一个右子树
  3. 是一个叶子节点
  4. 拥有左右两个子树（难点）

删除左右都有孩子的节点d。找到s = min(d->right) s是d的后继

s->right = delMin(d->right) 删除节点的右子树

s->left = d->left 删除节点的左子树

删除d，s是新的子树的根

二分搜索树 - 图3

  1. /*删除元素节点*/
  2. public void remove(E e){
  3.     root = remove(root,e);
  4. }
  5. private Node remove(Node node,E e){
  6.     if(node == null)
  7.         return null; //没找着
  8.     if(e.compareTo(node.e) <0){
  9.         node.left = remove(node.left , e);
  10.         return node;    
  11.     }else if(e.compareTo(node.e)>0){
  12.         node.right = remove(node.right,e);
  13.         return node;
  14.     }else{
  15.         // e == node.e
  16.         if(node.left == null){ //如果删除节点左子树为空
  17.             Node rightNode = node.right;
  18.             node.right = null;
  19.             size--;
  20.             return rightNode;
  21.         }
  22.         if(node.right == null){//如果删除节点右子树为空
  23.             Node leftNode = node.left;
  24.             node.left = null;
  25.             size--;
  26.             return leftNode;
  27.         }
  28.         //如果删除节点左右均不为空
  29.         Node successor = findMin(node.right);
  30.         successor.right = removeMin(node.right);
  31.         successor.left = node.left;
  33.         node.left = node.right = null;
  34.         return successor;
  35.     }
  36. }

完整代码

  1. import java.util.ArrayDeque;
  2. import java.util.LinkedList;
  3. import java.util.Queue;
  5. public class BST<E extends Comparable<E>> {
  6.     /**
  7.      * 结点
  8.      */
  9.     private class Node{
  10.         public E e;
  11.         public Node left;
  12.         public Node right;
  13.         public Node(E e){
  14.             this.e = e;
  15.             left = null;
  16.             right = null;
  17.         }
  18.     }
  19.     private Node root;
  20.     private int size;
  21.     public BST(){
  22.         root = null;
  23.         size=0;
  24.     }
  25.     public int size(){
  26.         return size;
  27.     }
  28.     public boolean isEmppty(){
  29.         return size==0;
  30.     }
  31.     /*添加元素*/
  32.     public void add(E e){
  33.         root = add(root, e);
  34.     }
  35.     //向以node为根的二分搜索树中插入元素E
  36.     private Node add(Node node, E e){
  37.         if(node == null){
  38.             size++;
  39.             return new Node(e);
  40.         }
  41.         if(e.compareTo(node.e) < 0){
  42.             node.left = add(node.left,e);//
  43.         }else if(e.compareTo(node.e)>0){
  44.             node.right = add(node.right,e);
  45.         }
  46.         return node;
  47.     }
  48.     /*查询元素*/
  49.     public boolean contains(E e){
  50.         return contains(root, e);
  51.     }
  52.     private boolean contains(Node node, E e){
  53.         if(node == null)//终止条件
  54.             return false;
  55.         if(e.compareTo(node.e) == 0)
  56.             return true; //找到了
  57.         else if(e.compareTo(node.e) <0)
  58.             return contains(node.left, e);
  59.         else
  60.             return contains(node.right, e);
  61.     }
  62.     /*前序遍历*/
  63.     public void preOrder(){
  64.         preOrder(root);
  65.     }
  66.     private void preOrder(Node node){
  67.         if(node == null)
  68.             return;
  69.         System.out.println(node.e);
  70.         preOrder(node.left);//访问左
  71.         preOrder(node.right);//访问右
  72.     }
  75.     /*中序遍历*/
  76.     public void midOrder(){
  77.         midOrder(root);
  78.     }
  79.     public void midOrder(Node node){
  80.         if(node == null)
  81.             return;
  82.         midOrder(node.left);
  83.         System.out.println(node.e);
  84.         midOrder(node.right);
  85.     }
  86.     /*后序遍历*/
  87.     public void postOrder(){
  88.         postOrder(root);
  89.     }
  90.     private void postOrder(Node node){
  91.         if(node == null)
  92.             return;
  93.         postOrder(node.left);
  94.         postOrder(node.right);
  95.         System.out.println(node.e);
  96.     }
  97.     /*寻找最大值与最小值*/
  98.     public E findMax(){
  99.         if(size==0)
  100.             throw new IllegalArgumentException("Is Empty!");
  101.         return findMax(root).e;
  102.     }
  103.     private Node findMax(Node node){
  104.         if(node.right == null)
  105.             return node;
  106.         return findMax(node.right);
  107.     }
  108.     public E findMin(){
  109.         if(size==0)
  110.             throw new IllegalArgumentException("Is Empty!");
  111.         return findMin(root).e;
  112.     }
  113.     private Node findMin(Node node){
  114.         if(node.left == null)
  115.             return node;
  116.         return findMin(node.left);
  117.     }
  118.     // 删除最大值与最小值
  119.     //删除以node为根的二分搜索树中的最大节点 返回删除节点后新的二分搜索树的根
  120.     public E removeMax(){
  121.         E res = findMax();
  122.         root = removeMax(root);
  123.         return res;
  124.     }
  125.     private Node removeMax(Node node){ //传入结点
  126.         if(node.right == null){//已经递归到底
  127.             Node leftNode = node.left; //接住结点的左树
  128.             node.left = null;
  129.             size--;
  130.             return leftNode;
  131.         }
  132.         node.right = removeMax(node.right);
  133.         return node;
  134.     }
  135.     private Node removeMin(Node node){ //传入结点
  136.         if(node.left == null){//已经递归到底
  137.             Node rightNode = node.right; //接住结点的左树
  138.             node.right = null;
  139.             size--;
  140.             return rightNode;
  141.         }
  142.         node.left = removeMin(node.left);
  143.         return node;
  144.     }
  146.     /*删除元素*/
  147.     public void remove(E e){
  148.         root = remove(root,e);
  149.     }
  150.     private Node remove(Node node,E e){
  151.         if(node == null)
  152.             return null; //没找着
  153.         if(e.compareTo(node.e) <0){
  154.             node.left = remove(node.left , e);
  155.             return node;
  156.         }else if(e.compareTo(node.e)>0){
  157.             node.right = remove(node.right,e);
  158.             return node;
  159.         }else{
  160.             // e == node.e
  161.             if(node.left == null){ //如果删除节点左子树为空
  162.                 Node rightNode = node.right;
  163.                 node.right = null;
  164.                 size--;
  165.                 return rightNode;
  166.             }
  167.             if(node.right == null){//如果删除节点右子树为空
  168.                 Node leftNode = node.left;
  169.                 node.left = null;
  170.                 size--;
  171.                 return leftNode;
  172.             }
  173.             //如果删除节点左右均不为空
  174.             Node successor = findMin(node.right);
  175.             successor.right = removeMin(node.right);
  176.             successor.left = node.left;
  178.             node.left = node.right = null;
  179.             return successor;
  180.         }
  181.     }
  183.     @Override
  184.     public String toString() {
  185.         StringBuilder res = new StringBuilder();
  186.         BSTString(root,0,res);
  187.         return res.toString();
  188.     }
  189. //    生成以node为根结点 深度为depth的二叉树的字符串
  190.     private void BSTString(Node node, int depth, StringBuilder res){
  191.         if(node == null){
  192.             res.append(BSTString(depth)+"null\n");
  193.             return;
  194.         }
  195.         res.append(BSTString(depth) + node.e + "\n");
  196.         BSTString(node.left, depth+1, res);
  197.         BSTString(node.right, depth+1, res);
  198.     }
  199.     private String BSTString(int depth){
  200.         StringBuilder res = new StringBuilder();
  201.         for(int i=0; i<depth; i++)
  202.             res.append("--");
  203.         return res.toString();
  204.     }
  205. }

Tree 前缀树

Trie是一个树形结构。是一种专门处理字符串匹配的数据结构，用来解决字符串集合中快速查找字符串的问题。

Trie也成为前缀树

Trie查询每条条目的事件复杂度与字典中一共多少条数目无关。

时间复杂度O(w),w为查询单词的长度。

核心思想：通过最大限度地减少字符串比较，用空间换时间，利用共同前缀提高查询效率

Trie特点

  1. 根节点没有任何字符,除根节点外每一个节点都只包含一个字符
  2. 根节点开始到某一结点路径上经过的字符连接起来就是搜索的字符串

构造

每个节点有若干指向下个节点的指针

  1. class Node{
  2.     char c;
  3.     Map<char,Node> next;
  4. }

插入元素

二分搜索树 - 图4

从跟节点开始，将单词的每个字母逐一插入 Trie树。插入前先看字母对应的节点是否存在，存在则共享该节点，不存在则创建对应的节点。

  1. //添加一个单词word
  2. public void add(String word){
  3.     Node cur = root;
  4.     for(int i=0; i<word.length(); i++){//使用循环的方式添加映射
  5.         char c =word.charAt(i);
  6.         if(cur.next.get(c)==null){
  7.             cur.next.put(c,new Node());
  8.         }
  9.         cur = cur.next.get(c);
  10.     }
  11.     if(!cur.isWord){//如果单词没有存在
  12.         cur.isWord = true;
  13.         size++;
  14.     }
  15. }

查询操作

二分搜索树 - 图5

从根节点开始遍历，如果下一个节点不包含直接返回false，需要注意的是最后的返回值不是直接返回true而是cur.isWord，因为比如pan、panda但是只添加了panda如果返回值为true那么pan也会搜索成功。所以应该返回Node的isWord属性

  1. //查询单词word
  2. public boolean contains(String word){
  3.     Node cur = root;
  4.     for(int i=0; i<word.length(); i++){
  5.         char c = word.charAt(i);
  6.         if(cur.next.get(c)==null)
  7.             return false;
  8.         cur = cur.next.get(c);
  9.     }
  10.     return cur.isWord;//Important
  11. }

简单模式匹配

p.. = pan .可以代表任何一个字母

  1. //匹配单词word
  2. public boolean search(String word){
  3.     return match(root,word,0);
  4. }
  5. /*三个参数节点|单词|单词指针*/
  6. private boolean match(Node node, String word, int index){
  7.     if(index==word.length())
  8.         return node.isWord;
  10.     char c = word.charAt(index); //获取当前指针
  11.     if(c!='.'){
  12.         if(node.next.get(c) == null) //如果不是.看下一个是不是空 不是空接着下一个节点
  13.             return false;
  14.         return match(node.next.get(c),word,index+1);
  15.     }else{
  16.         for(char nextChar:node.next.keySet())
  17.             if(match(node.next.get(nextChar),word,index+1))
  18.                 return true;
  19.         return false;
  20.     }
  21. }
  1. import java.util.TreeMap;
  3. public class Trie {
  4.     private class Node{
  5.         public boolean isWord; //是否找到了
  6.         public TreeMap<Character,Node> next;
  7.         public Node(boolean isWord){
  8.             this.isWord = isWord;
  9.             next = new TreeMap<>();
  10.         }
  11.         public Node(){
  12.             this(false);
  13.         }
  14.     }
  15.     private Node root;
  16.     private int size;
  18.     public Trie(){ //构造函数
  19.         root = new Node();
  20.         size=0;
  21.     }
  23.     public int getSize(){
  24.         return this.size;
  25.     }
  26.     //添加一个单词word
  27.     public void add(String word){
  28.         Node cur = root;
  29.         for(int i=0; i<word.length(); i++){//使用循环的方式添加映射
  30.             char c =word.charAt(i);
  31.             if(cur.next.get(c)==null){
  32.                 cur.next.put(c,new Node());
  33.             }
  34.             cur = cur.next.get(c);
  35.         }
  36.         if(!cur.isWord){//如果单词没有存在
  37.             cur.isWord = true;
  38.             size++;
  39.         }
  40.     }
  42.     //查询单词word
  43.     public boolean contains(String word){
  44.         Node cur = root;
  45.         for(int i=0; i<word.length(); i++){
  46.             char c = word.charAt(i);
  47.             if(cur.next.get(c)==null)
  48.                 return false;
  49.             cur = cur.next.get(c);
  50.         }
  51.         return cur.isWord;//Important
  52.     }
  54.     //匹配单词word
  55.     public boolean search(String word){
  56.         return match(root,word,0);
  57.     }
  58.     /*三个参数节点|单词|单词指针*/
  59.     private boolean match(Node node, String word, int index){
  60.         if(index==word.length())
  61.             return node.isWord;
  63.         char c = word.charAt(index); //获取当前指针
  64.         if(c!='.'){
  65.             if(node.next.get(c) == null) //如果不是.看下一个是不是空 不是空接着下一个节点
  66.                 return false;
  67.             return match(node.next.get(c),word,index+1);
  68.         }else{
  69.             for(char nextChar:node.next.keySet())
  70.                 if(match(node.next.get(nextChar),word,index+1))
  71.                     return true;
  72.             return false;
  73.         }
  74.     }
  77. }

删除操作

二分搜索树 - 图6

应用

前缀匹配

image.png

字符串检索


给出 N 个单词组成的熟词表，以及一篇全用小写英文书写的文章，按最早出现的顺序写出所有不在熟词表中的生词。
检索/查询功能是Trie树最原始的功能。给定一组字符串，查找某个字符串是否出现过，思路就是从根节点开始一个一个字符进行比较：

  • 如果沿路比较，发现不同的字符，则表示该字符串在集合中不存在。
  • 如果所有的字符全部比较完并且全部相同，还需判断最后一个节点的标志位（标记该节点是否代表一个关键字）。