科普文：算法和数据结构系列【死磕字典树：字典树的升级版三叉树Ternary Search Tree优化】

概叙

科普文：算法和数据结构系列【死磕字典树：来一个英文字母游戏】-CSDN博客

科普文：算法和数据结构系列【高效的字符串检索结构：字典树Trie树原理、应用及其java示例代码解读】-CSDN博客

‌原理‌：
Trie树利用字符串之间的公共前缀来减少不必要的字符串比较，从而提高查询效率。每个节点代表一个字符，从根节点到某一节点的路径上经过的字符连接起来，就是该节点对应的字符串。

‌优缺点‌：
优点：查询效率高，最大限度地减少无谓的字符串比较；支持前缀匹配，适合用于搜索引擎的词频统计等场景。
缺点：空间复杂度可能较高，特别是当存储大量字符串时。
空间消耗：对于不共享前缀的字符串集合，Trie 可能消耗大量内存。
不适合动态数据：如果需要频繁地插入和删除字符串，维护 Trie 的代价可能较高。
复杂度‌：
‌时间复杂度‌：插入、查找和前缀匹配操作的时间复杂度通常为O(L)，其中L是字符串的长度。
‌空间复杂度‌：取决于存储的字符串数量和长度。

‌注意事项‌：实现时需要考虑内存使用，避免浪费空间。

优化方向 节省空间：　　压缩字典树，但是维护成本更高;　　三分搜索树
压缩前缀树：合并只有一个子节点的节点，可以减少内存使用。
Ternary Search Tree：每个节点有三个子节点，可以在某些情况下提供更好的平衡。
使用哈希表：在每个节点使用哈希表而不是数组来存储子节点，可以处理更大的字符集。

Ternary Search Tree三叉树如何优化字典树？

Ternary Search Tree（三元搜索树）是一种高效的数据结构，用于存储和检索字符串集合。与字典树（Trie）相比，三元搜索树在某些方面提供了更优的性能和空间利用率。

三元搜索树通过减少节点数量、提高空间利用率和搜索效率等方式来优化字典树。然而，选择哪种数据结构取决于具体的应用场景和需求。

在某些情况下，字典树可能更合适；而在其他情况下，三元搜索树可能提供更好的性能。

以下是如何使用三元搜索树来优化字典树的一些方法：

1. ‌减少节点数量‌：

   • 字典树中，每个字符通常对应一个节点，这导致节点数量可能非常多，尤其是当字典中的字符串很长或有很多共享前缀时。
   • 三元搜索树通过在每个节点中存储三个指针（分别指向小于、等于和大于当前字符的子树）和一个字符来减少节点数量。这样，一个节点就可以表示多个字符的分支，从而减少了整体节点数量。

2. ‌空间利用率‌：

   • 字典树中，很多节点可能只包含一个子节点，这造成了空间上的浪费。
   • 三元搜索树通过更紧凑地组织节点，减少了这种空间浪费。每个节点都尽可能地包含更多的信息，使得树的结构更加紧凑。

3. ‌搜索效率‌：

   • 字典树的搜索效率与字符串的长度成正比，因为需要逐层遍历节点。
   • 三元搜索树利用字符的比较来指导搜索，每次比较都可以将搜索范围缩小到三分之一（理论上），从而提高了搜索效率。特别是在处理大量字符串或长字符串时，这种效率提升尤为明显。

4. ‌平衡性‌：

   • 字典树并不总是平衡的，特别是当插入的字符串顺序不随机时。不平衡的树会导致搜索性能下降。
   • 三元搜索树在构造时就考虑到了平衡性，通过合理地分配字符到子树中，可以保持树的平衡，从而确保稳定的搜索性能。

5. ‌前缀搜索‌：

   • 字典树天然支持前缀搜索，因为共享前缀的字符串在树中共享节点。
   • 三元搜索树也可以通过适当的修改来支持前缀搜索，但可能需要额外的数据结构或算法来高效地实现这一功能。

6. ‌实现复杂度‌：

   • 字典树的实现相对简单，但可能不适用于所有场景。
   • 三元搜索树的实现可能更复杂一些，但提供了更高的灵活性和性能。在实现时，需要仔细考虑节点的数据结构、插入和搜索算法等。

字典树升级版三叉树的java实现

三节点定义：TrieThreeNode

class TrieThreeNode {
    String labels;// 单词前缀
    // 三个子节点，分别用left, middle, right来表示
    // 这里可以根据实际需求来命名，比如left, mid, right或者first, second, third等
    TrieThreeNode left;
    TrieThreeNode middle;
    TrieThreeNode right;

    // 标志当前节点是否是一个单词的结束
    boolean isEndOfWord;

    // 构造函数
    public TrieThreeNode(String labels) {
        this.labels = labels;
        this.left = null;
        this.middle = null;
        this.right = null;
        this.isEndOfWord = false;
    }
    // 检查节点是否为叶子节点
    public boolean isLeaf() {
        return  this.left == null && this.middle == null && this.right == null;
    }

    @Override
    public String toString() {
        StringBuilder stringBuilder = new StringBuilder("{");
        stringBuilder.append("labels=").append(labels).append(",");
        stringBuilder.append("isEndOfWord=").append(isEndOfWord).append(",");
        stringBuilder.append("isLeaf=").append(isLeaf()).append(",");
        //stringBuilder.append("ChildrenCount=").append(getChildrenCount()).append(",");
        stringBuilder.append("left=").append(left == null  ? "[]" : left).append(",");
        stringBuilder.append("middle=").append(middle == null  ? "[]" : middle).append(",");
        stringBuilder.append("right=").append(right == null  ? "[]" : right);
        stringBuilder.append("}");
        return stringBuilder.toString();
    }
}

TrieThreeNode 类代表三元搜索树（Ternary Search Tree, TST）中的一个节点。这种树是字典树（Trie）的一种变体，用于高效地存储和检索字符串。

成员变量

• String labels;：存储节点代表的单词前缀（或字符）。在三元搜索树中，每个节点通常只存储一个字符，但这里的实现选择存储整个前缀，这可能是为了简化某些操作或适应特定的应用场景。
• TrieThreeNode left;：指向左子节点的引用，用于存储小于当前节点字符的字符所对应的子树。
• TrieThreeNode middle;：指向中子节点的引用，用于存储等于当前节点字符的字符所对应的子树。
• TrieThreeNode right;：指向右子节点的引用，用于存储大于当前节点字符的字符所对应的子树。
• boolean isEndOfWord;：一个布尔标志，表示当前节点是否是一个单词的结束。

构造函数

• public TrieThreeNode(String labels)：构造函数接受一个字符串作为参数，用于初始化节点的 labels 成员变量，并将 left、middle、right 子节点初始化为 null，同时将 isEndOfWord 标志设置为 false。

方法

• public boolean isLeaf()：此方法检查当前节点是否为叶子节点。在三元搜索树中，叶子节点是没有子节点的节点。该方法通过检查 left、middle 和 right 是否都为 null 来实现。
• @Override public String toString()：重写 toString 方法以返回节点的字符串表示形式。该方法构建一个包含节点所有成员变量值的字符串，便于调试和可视化。

注意事项

• 在这个实现中，labels 成员变量被用来存储整个前缀，而不是单个字符。这可能与典型的三元搜索树实现有所不同，其中每个节点通常只存储一个字符。这种设计选择可能取决于特定的应用场景或性能考虑。
• toString 方法中使用了 StringBuilder 来高效地构建字符串。这是一个良好的实践，因为字符串在 Java 中是不可变的，使用 StringBuilder 可以避免创建大量的临时字符串对象。
• 类中没有提供插入、搜索或删除节点的方法。这些方法通常会在包含 TrieThreeNode 类的更大上下文中实现，例如在一个 TernarySearchTree 类中。
• isLeaf 方法用于检查节点是否为叶子节点，这在某些树操作中可能是有用的，例如遍历或剪枝。

三节点字典树主类：

package com.zxx.study.algorithm.datastruct.DataStructures.mtree.trie;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhouxx
 * @create 2025-01-18 9:37
 */
public class TrieThreeWay {
    private TrieThreeNode root;

    public TrieThreeWay() {
        root = new TrieThreeNode("");
    }

    // 插入一个单词到三叉树Trie中
    public void insert(String word) {
        if (search(word)) {
            return;//不重复插入
        }
        TrieThreeNode current = root;
        for (char c : word.toCharArray()) {
            TrieThreeNode nextNode = null;
            if (c < 'm') {
                nextNode = current.left;
            } else if (c <= 'z') {
                nextNode = current.middle;
            } else {
                nextNode = current.right;
            }

            if (nextNode == null) {
                if (c < 'm') {
                    current.left = new TrieThreeNode(String.valueOf(c));
                    current = current.left;
                } else if (c <= 'z') {
                    current.middle = new TrieThreeNode(String.valueOf(c));
                    current = current.middle;
                } else {
                    current.right = new TrieThreeNode(String.valueOf(c));
                    current = current.right;
                }
            } else {
                current = nextNode;
            }
        }
        current.isEndOfWord = true;
        System.out.println(word + " insert TrieNode : " + current);
        System.out.println(word + " insert TrieNode/root : " + root);
    }

    // 删除一个单词从三叉树Trie中
    public void delete(String word) {
        if (search(word)) {
            //存在才进行删除
            delete(root, word, 0);
        }
    }

    private boolean delete(TrieThreeNode current, String word, int index) {
        if (index == word.length()) {
            if (!current.isEndOfWord) {
                return false; // 单词不存在
            }
            current.isEndOfWord = false;
            return current.isLeaf();
        }

        char c = word.charAt(index);
        TrieThreeNode nextNode = null;
        if (c < 'm') {
            nextNode = current.left;
        } else if (c <= 'z') {
            nextNode = current.middle;
        } else {
            nextNode = current.right;
        }

        if (nextNode == null) {
            return false; // 单词不存在
        }

        boolean shouldDeleteCurrentNode = delete(nextNode, word, index + 1);

        if (shouldDeleteCurrentNode) {
            if (c < 'm') {
                current.left = null;
            } else if (c <= 'z') {
                current.middle = null;
            } else {
                current.right = null;
            }
            return current.isLeaf() && !current.isEndOfWord;
        }
        return false;
    }


    // 查找一个单词是否存在于三叉树Trie中
    public boolean search(String word) {
        TrieThreeNode current = searchNode(word);
        return current != null && current.isEndOfWord;
    }

    // 查找是否存在以某个前缀开头的单词
    public boolean startsWith(String prefix) {
        TrieThreeNode current = searchNode(prefix);
        return current != null;
    }

    private TrieThreeNode searchNode(String word) {
        //word = word.toLowerCase();
        TrieThreeNode current = root;
        for (char c : word.toCharArray()) {
            if (c <= 'm') {
                if (current.left == null) {
                    return null;
                }
                current = current.left;
            } else if (c <= 'z') {
                if (current.middle == null) {
                    return null;
                }
                current = current.middle;
            } else {
                if (current.right == null) {
                    return null;
                }
                current = current.right;
            }
        }
        return current;
    }

    // 拼写检查：返回是否拼写正确
    public boolean spellCheck(String word) {
        return search(word);
    }

    // 自动补全：返回所有以指定前缀开头的单词
    public List<String> autoComplete(String prefix) {
        List<String> result = new ArrayList<>();
        TrieThreeNode prefixNode = findPrefixNode(prefix);
        if (prefixNode != null) {
            collectAllWords(prefixNode, new StringBuilder(prefix), result);
        }
        return result;
    }

    // 查找前缀节点
    private TrieThreeNode findPrefixNode(String prefix) {
        TrieThreeNode current = root;
        for (char c : prefix.toCharArray()) {
            TrieThreeNode nextNode;
            if (c < 'm') {
                nextNode = current.left;
            } else if (c <= 'z') {
                nextNode = current.middle;
            } else {
                nextNode = current.right;
            }
            if (nextNode == null) {
                return null; // 前缀不存在于Trie树中
            }
            current = nextNode;
        }
        return current;
    }

    private void collectAllWords(TrieThreeNode node, StringBuilder prefix, List<String> result) {
        if (node.isEndOfWord) {
            result.add(prefix.toString());
        }
        if (node.left != null) {
            prefix.append(node.left.labels);
            collectAllWords(node.left, prefix, result);
            prefix.deleteCharAt(prefix.length() - 1);
        }
        if (node.middle != null) {
            prefix.append(node.middle.labels);
            collectAllWords(node.middle, prefix, result);
            prefix.deleteCharAt(prefix.length() - 1);
        }
        if (node.right != null) {
            prefix.append(node.right.labels);
            collectAllWords(node.right, prefix, result);
            prefix.deleteCharAt(prefix.length() - 1);
        }
    }

    // 合并只有一个节点的子树（优化空间使用）
    public void mergeSingleNodeSubtrees() {
        mergeSingleNodeSubtrees(root);
    }

    private void mergeSingleNodeSubtrees(TrieThreeNode node) {
        if (node == null) {
            return;
        }

        // 检查左子树
        if (node.left != null && isSingleNodeSubtree(node.left)) {
            mergeNode(node, node.left);
            node.left = null;
        } else {
            mergeSingleNodeSubtrees(node.left);
        }

        // 检查中子树
        if (node.middle != null && isSingleNodeSubtree(node.middle)) {
            mergeNode(node, node.middle);
            node.middle = null;
        } else {
            mergeSingleNodeSubtrees(node.middle);
        }

        // 检查右子树
        if (node.right != null && isSingleNodeSubtree(node.right)) {
            mergeNode(node, node.right);
            node.right = null;
        } else {
            mergeSingleNodeSubtrees(node.right);
        }
    }

    private boolean isSingleNodeSubtree(TrieThreeNode node) {
        return node != null && node.isLeaf() &&
                (node.left == null || node.left.isLeaf() && node.left.left == null && node.left.middle == null && node.left.right == null) &&
                (node.middle == null || node.middle.isLeaf() && node.middle.left == null && node.middle.middle == null && node.middle.right == null) &&
                (node.right == null || node.right.isLeaf() && node.right.left == null && node.right.middle == null && node.right.right == null);
    }

    //mergeNode方法简单地将子节点的标签附加到父节点上，并继承子节点的isEndOfWord状态。
    // 这种合并方式可能不适用于所有情况，特别是当标签包含有意义的信息（如字符或字符串）时。
    // 在实际应用中，你可能需要根据具体情况来定制合并逻辑。
    private void mergeNode(TrieThreeNode parent, TrieThreeNode child) {
        parent.labels += child.labels;
        parent.isEndOfWord = child.isEndOfWord;
    }

}

TrieThreeWay类是一个实现了三元搜索树结构的字典树，用于存储字符串并支持插入、删除、搜索、自动补全和拼写检查等操作。

成员变量

• private TrieThreeNode root;：指向根节点的引用，根节点不存储实际字符，作为树的入口点。

构造函数

• public TrieThreeWay()：构造函数初始化根节点为一个空的TrieThreeNode对象。

方法

插入（insert）

• public void insert(String word)：将一个单词插入到三叉树Trie中。如果单词已存在，则不进行插入。
  • 遍历单词的每个字符，根据字符的大小关系选择进入左子树、中子树或右子树。
  • 如果当前字符对应的子节点不存在，则创建新的TrieThreeNode节点并连接到当前节点。
  • 遍历完成后，将最后一个节点标记为单词的结束。

删除（delete）

• public void delete(String word)：从三叉树Trie中删除一个单词。如果单词存在，则进行删除操作。
  • 递归地查找单词的每个字符，直到找到最后一个字符对应的节点。
  • 将该节点标记为非单词结束节点。
  • 如果该节点是叶子节点且不是单词结束节点，则递归地向上删除该节点，直到遇到非叶子节点或根节点。

搜索（search）

• public boolean search(String word)：查找一个单词是否存在于三叉树Trie中。
  • 调用searchNode方法查找单词对应的节点。
  • 如果找到的节点不为空且是单词结束节点，则返回true，否则返回false。

前缀搜索（startsWith）

• public boolean startsWith(String prefix)：查找是否存在以某个前缀开头的单词。
  • 调用searchNode方法查找前缀对应的节点。
  • 如果找到的节点不为空，则返回true，否则返回false。

拼写检查（spellCheck）

• public boolean spellCheck(String word)：返回是否拼写正确，即单词是否存在于Trie中。
  • 直接调用search方法进行检查。

自动补全（autoComplete）

• public List<String> autoComplete(String prefix)：返回所有以指定前缀开头的单词。
  • 调用findPrefixNode方法查找前缀对应的节点。
  • 从该节点开始，递归地收集所有以该前缀开头的单词。

辅助方法

• private TrieThreeNode searchNode(String word)：辅助方法，用于查找单词或前缀对应的节点。
• private TrieThreeNode findPrefixNode(String prefix)：辅助方法，用于查找前缀对应的节点。
• private void collectAllWords(TrieThreeNode node, StringBuilder prefix, List<String> result)：辅助方法，用于递归地收集所有以指定前缀开头的单词。
• public void mergeSingleNodeSubtrees()：优化空间使用的方法，合并只有一个节点的子树。
  • 递归地检查每个节点的子树，如果子树只有一个节点且是叶子节点，则将该节点的标签合并到父节点上，并删除子节点。
  • 

注意事项

• 在这个实现中，TrieThreeNode类的labels成员变量被用来存储整个前缀（或字符），而不是单个字符。这可能与典型的三元搜索树实现有所不同，但适应了特定的应用场景。
• mergeSingleNodeSubtrees方法提供了一种优化空间使用的手段，但合并逻辑可能需要根据实际应用场景进行定制。
• 该类提供了丰富的操作接口，包括插入、删除、搜索、自动补全和拼写检查等，适用于需要高效存储和检索字符串的场景。

测试结果：

这里还有一个小问题，眼尖的朋友是否已经发现，欢迎留言交流。