算法5.5 三向单词查找树

算法描述

  • R向查找树每个结点保存R条链接,会有大量空间损耗,而三向单词查找函数TST,采用类似BST的结构,每个结点一个字符,三条链接,一个值,链接对应小于,等于,大于值的结点,TST中字符是显示保存的

实现

  1. public class TST<Value>{
  2.     private Node root;
  3.     private class Node{
  4.         char c;
  5.         Node left, mid, right;//三个子树
  6.         Value val;//显示保存字符
  7.     }
  9.     public Value get(String key){
  10.         Node x = get(root, key, 0);
  11.         if(x == null) return null;
  12.         return (Value)x.val;
  13.     }
  14.     private Value get(Node x, String key, int d){
  15.         if(x == null) return null;
  16.         char c = key.charAt[d];
  17.         if(c < x.c) return get(x.left, key, d+1);
  18.         else if(c > x.c) return get(x.right, key, d+1);
  19.         else if(d < key.length()-1) return get(x.mid, key, d+1);
  20.         else return x;
  21.     }
  23.     public void put(String key, Value val){ root = put(root, key, val, 0);}
  24.     private Node put(Node x, String key, Value val, int d){
  25.         char c = key.charAt(d);
  26.         if(x == null){ x = new Node(); x.c = c};
  27.         if(c < x.c) x.left = put(x.left, key, val, d);
  28.         else if(c > x.c) x.left = put(x.right, key, val, d);
  29.         else if(d < key.length()-1) put(x.mid, key, d+1);
  30.         else x.val = val;//键存在,更新值
  31.         return x;
  32.     }
  33. }

算法分析

  • N个平均长度w的字符串构造的TST中链接总数在3N到3Nw之间
  • 查找成本:未命中查找平均比较~lnN次,一次插入或命中查找会比较一次被查找键中的每个字符

字符串查找算法

string.png