线段树和Trie

线段树和Trie

1.为什么使用线段树

最经典的线段树问题:RMQ(区间最值问题)和区间求和

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-dv3DZ3j8-1639912767031)(D:\HJ2012\java数据结构\无标题.png)]线段树和Trie

2.构建线段树

1>线段树不是完全二叉树,是平衡二叉树。可以使用数组表示树的结点

2>给定一个数组arr,获取生成线段树的高度

2的(h-1)次方 ≥ arr. length的最小值

3>生成的线段树的结点个数最多为: 2h次方 − 1

4>生成线段树

 /**
     * 构建线段树
     *
     * @param start 区间的开始
     * @param end   区间的结尾
     * @param index 线段树对应[start:end]区间的索引
     */
    private void buildingSegmentTree(int start, int end, int index) {
        // 1、递归到底的情况
        if (start == end) {
            this.data[index] = this.source[start];
            return;
        }

        // 2、递归操作
        int mid = start + (end - start) / 2;
        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        buildingSegmentTree(start, mid, leftIndex);
        buildingSegmentTree(mid + 1, end, rightIndex);
        this.data[index] = this.merger.merge(this.data[leftIndex], this.data[rightIndex]);
    }

注意:int mid = (start + end)/2;可能会超范围,所以使用 int mid = start +(end -start)/2

此构建线段树的方法只支持求和操作,为了具有通用性,可以设计一个融合接口Merge

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

3、查询操作

    /**
     * 进行查询操作
     *
     * @param start 线段树结点所表示区间的start
     * @param end   线段树结点所表示区间的end
     * @param index 线段树上结点的索引
     * @param from  查询区间的开始
     * @param to    查询区间的结尾
     * @return
     */
    private T query(int start, int end, int index, int from, int to) {
        // 1、递归到底的情况
        if (start == from && end == to) {
            return this.data[index];
        }
        // 2、递归操作(【1】 左边完全不包含  【2】右边完全不包含  【3】左右都包含)
        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        int mid = start + (end - start) / 2;
        if (from > mid) {
            return query(mid + 1, end, rightIndex, from, to);
        } else if (to <= mid) {
            return query(start, mid, leftIndex, from, to);
        } else {
            // 左边
            T leftValue = query(start, mid, leftIndex, from, mid);
            // 右边
            T rightValue = query(mid + 1, end, rightIndex, mid + 1, to);
            return this.merger.merge(leftValue, rightValue);
        }
    }

4.更新操作

 /**
     * 更新源数组索引为index位置的值为val
     *
     * @param site 索引
     * @param val  值
     */
    public void update(int site, T val) {
        if (site < 0 || site >= this.source.length) {
            throw new IllegalArgumentException("index is invalid!");
        }
        // 重新渲染线段树
        update(0, this.source.length - 1, 0, site, val);
    }

    private void update(int start, int end, int index, int orindex, T val) {
        // 1、递归到底的情况
        if (start == end && start == orindex) {
            this.source[orindex] = this.data[index] = val;
            return;
        }
        // 2、递归操作
        int mid = start + (end - start) / 2;
        int leftIndex = 2 * index + 1;
        int rightIndex = leftIndex + 1;
        if (mid < orindex) {
            update(mid + 1, end, rightIndex, orindex, val);
        } else {
            update(start, mid, leftIndex, orindex, val);
        }
        this.data[index] = this.merger.merge(this.data[leftIndex], this.data[rightIndex]);
    }

5、Trie

在计算机科学中,trie,又称前缀树或字典树。与二叉查找树不同,值不是直接保存在节点中,而是由节点在树中的位置

决定。一个节点的所有子孙都有相同的前缀,也就是这个节点对应的字符串,而根节点对应空字符串。

Trie的典型应用是用于统计,它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较
线段树和Trie

6、Trie结点结构

每个结点都有若干指向下个结点的指针

 // 结点
    private class Node {
        boolean isWord;// 是否是单词
        Map<Character, Node> next; //该结点下所有的字符对应的结点

        Node() {
            isWord = false;
            next = new HashMap<>();
        }
    }

    private Node root;// 根
    private int size; // 单词个数

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

    public int getSize() {
        return this.size;
    }

7、Trie添加操作

// 添加操作
    public void addStr(String str) {
        if (str == null || str.length() == 0) {
            return;
        }
        Node cur = root;
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.keySet().contains(c)) {
                children.put(c, new Node());
            }
            cur = children.get(c);
        }
        if (!cur.isWord) {
            cur.isWord = true;
            this.size += 1;
        }
    }

8.判断是否存在指定的单词

 // 判断是否存在指定的单词
    public boolean matchWord(String word) {
        if (word == null || word.length() == 0) {
            return false;
        }
        Node cur = root;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.keySet().contains(c)) {
                return false;
            }
            cur = children.get(c);
        }
        return cur.isWord;
    }

9.判断是否存在以pre开始的单词

  // 判断是否存在以pre开始的单词
    public boolean matchStartPre(String pre) {
        if (pre == null || pre.length() == 0) {
            return false;
        }
        Node cur = root;
        for (int i = 0; i < pre.length(); i++) {
            char c = pre.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.keySet().contains(c)) {
                return false;
            }
            cur = children.get(c);
        }
        return true;
    }

10.模糊匹配

    public boolean search(String express) {
        if (express == null || express.length() == 0) {
            return false;
        }
        return match(root, express, 0);
    }

    /**
     * @param node    当前结点
     * @param express 表达式
     * @param index   表达式中匹配字符的索引
     * @return
     */
    private boolean match(Node node, String express, int index) {
        if (index == express.length()) {
            return true;
        }
        char c = express.charAt(index);
        if (c != '.') {
            Map<Character, Node> children = node.next;
            if (!children.keySet().contains(c)) {
                return false;
            }
            return match(children.get(c), express, index + 1);
        } else {
            Map<Character, Node> children = node.next;
            Set<Character> set = children.keySet();
            for (Character chr : set) {
                if (match(children.get(chr), express, index + 1)) {
                    return true;
                }
            }
            return false;
        }
    }

11.删除操作

1、如果单词是另外一个单词的前缀,只需将该单词最后一个结点的isWord修改成false

2、如果单词的所有字符都没有分支,删除整个单词

3、如果单词除了最后一个字符,其他的字符存在多个分支

4、对第2种情况的补充:如果单词的所有字符都没有分支,但是存在前缀作为单词的情况,例如:pan,panda,在删除 panda时,使用第三种情况进行处理(node.next.size() == 1 && node.isword)
线段树和Trie

  public List<String> matchStartExpressWords(String express) {
        List<String> list = new ArrayList<>();
        if (express != null && express.length() != 0) {
            match(root, express, 0, list);
        }
        return list;
    }

    /**
     * @param node    当前结点
     * @param express 表达式
     * @param index   表达式中匹配字符的索引
     * @param list    存储结果
     */
    private void match(Node node, String express, int index, List<String> list) {
        // 递归终止条件
        if (express.length() == index) {
            findWords(node, list);
            return;
        }

        // 递归操作
        char c = express.charAt(index);
        if (c != '.') {
            Map<Character, Node> children = node.next;
            if (!children.containsKey(c)) {
                return;
            }
            match(children.get(c), express, index + 1, list);
        } else {
            Map<Character, Node> children = node.next;
            for (Character chr : children.keySet()) {
                match(children.get(chr), express, index + 1, list);
            }
        }
    }

    //  递归操作,获取单词
    public void findWords(Node node, List<String> list) {
        if (node.isWord) {
            list.add(node.val);
        }
        // 递归终止条件
        if (node.next.size() == 0) {
            return;
        }
        Map<Character, Node> children = node.next;
        Set<Character> keys = children.keySet();
        for (Character key : keys) {
            findWords(children.get(key), list);
        }
    }

    // 删除单词
    public void deleteWord(String word) {
        if (word == null || word.length() == 0) {
            throw new IllegalArgumentException("word is invalid");
        }
        Node cur = this.root;
        Node multiNode = null; // 记录分叉结点
        int multiIndex = -1; // 记录分叉字符的索引
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            Map<Character, Node> children = cur.next;
            if (!children.containsKey(c)) {
                return;
            } else {
                Node node = children.get(c);
                if (node.next.size() > 1 || (node.next.size() == 1 && node.isWord)) {
                    multiNode = node;
                    multiIndex = i;
                }
                cur = node;
            }
        }
        // 真正的删除操作
        if (cur.isWord) {
            if (cur.next.size() > 0) {
                cur.isWord = false;
            } else if (multiNode == null) {
                this.root.next.remove(word.charAt(0));
            } else {
                multiNode.next.remove(word.charAt(multiIndex + 1));
            }
            this.size -= 1;
        }
    }

12.测试

 public static void main(String[] args) {
        String[] strs = {"pand", "panda", "service", "ex_serviceman", "gun", "army", "oil","coal", "petol", "pan"};
        Trie trie = new Trie();
        Arrays.stream(strs).forEach(item -> trie.addStr(item));
//        System.out.println(trie.getSize());
//        System.out.println(trie.matchWord("pan"));
//        System.out.println(trie.search("p.l"));
        // 匹配所有以express表达式为前缀的字符串
//        List<String> list = trie.matchStartExpressWords("pan");
//        list.stream().forEach(System.out::println);
        trie.deleteWord("pand");
        System.out.println(trie.matchWord("panda"));
        System.out.println(trie.matchWord("pand"));
        System.out.println(trie.matchWord("pan"));
    }
上一篇:五一 考试二


下一篇:【字符串】