查找-多路查找详解篇

深藏阁楼爱情的钟 2023-10-14 08:51 26阅读 0赞

## 多路查找树 ##

多路查找树（Multway Search Tree）是一种高级的树形数据结构，它
    允许每个节点有多个子节点（通常大于等于2）。多路查找树的每个节点
    可以存储多个关键字和对应的值。

### 分类 ###

2-3树（2-3 Tree）：
    2-3树是一种最简单的多路查找树，每个节点可以存储1个或2个关键字，
    并有2个或3个子节点。
    2-3树的特点是所有叶子节点都在同一层，且根节点到每个叶子节点的
    路径长度相等，保持树的平衡性。
    
    B-树（B-tree）：
    B-树是一种平衡的多路查找树，每个节点可以存储多个关键字，并有相
    应数量的子节点。
    B-树的特点是节点的关键字按照升序排列，具有高度平衡的特性，主要
    用于在磁盘等外部存储设备中高效存储和检索数据。
    
    B+树（B+ tree）：
    B+树是B-树的一种变种，在B-树的基础上做了一些优化，特别适合于范
    围查询和顺序访问。
    B+树的特点是只有叶子节点存储了真实数据，而内部节点仅用于索引，
    叶子节点通过指针连接形成一个链表，方便范围查询。
    
    B树（B-tree）：
    B*树也是B-树的一种变种，与B+树类似，它在B-树的基础上做了一些改
    进。
    B*树通过在非叶子节点中存储部分关键字，扩大了节点的使用率，减少
    了磁盘访问次数，并提高了空间和时间的效率。
    
    Trie树（字典树或前缀树）：
    Trie树是一种特殊的多路查找树，在处理字符串和前缀匹配的情况下非
    常有用。
    Trie树的特点是每个节点代表一个字符，从根节点到叶子节点的路径可
    以表示一个完整的字符串。
    
    除此以外，还有如2-3-4树、2-3-4-树、B*+树等。每种多路查找树在
    平衡性、存储结构、查询性能等方面可能有所不同，选择合适的多路查
    找树取决于应用需求和数据特点。对于大规模的外部存储数据，B-树和
    B+树是常见的选择；对于高效的字符串匹配和前缀查询，Trie树是一种
    有效的数据结构。

### 详细介绍 ###

![在这里插入图片描述][40cdddf12c9b45b0bb965614e6171157.png]

#### 2-3树（2-3 Tree） ####

2-3树是一种平衡的多路查找树，每个节点可以存储1个或2个关键字，并有2个
    或3个子节点。以下是关于2-3树的详细介绍：

![在这里插入图片描述][2a437733152f49d4abfcc940cd2f91f2.png]

##### 结构特点： #####

2-3树由节点组成，每个节点可以存储1个或2个关键字，这些关键字按升序排列。
    每个节点有2个或3个子节点，对应于存储的关键字个数。
    所有叶子节点都在同一层，且根节点到每个叶子节点的路径长度相等，保持树的
    平衡性。

##### 插入操作： #####

1、当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
    2、如果节点已满（即已有两个关键字），则需要进行节点分裂操作。将中间较
    	大的关键字移动到上一层的父节点，并将两个剩余的关键字分别创建为新的
    	子节点。
    3、如果节点还没有满，则直接将关键字插入到正确的位置。

![在这里插入图片描述][dc77927a94d74f80b89752fee346fa0d.png]

##### 删除操作： #####

当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
    	如果该节点是叶子节点，直接删除关键字即可。如果该节点是内部节点，有
    		几种情况需要处理：
    	如果该节点有2个关键字，则可以直接删除关键字，不需要做其他操作。
    	如果该节点有1个关键字：
    	如果其兄弟节点有2个关键字，则可以借用兄弟节点的一个关键字，并进行
    		相关的调整。
    	如果其兄弟节点也只有1个关键字，则需要进行合并操作，将关键字和子节
    		点合并到一起。

##### 查询操作： #####

2-3树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，
    向左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。

##### 强调 #####

2-3树的特点在于其每个节点可以存储多个关键字，这样可以减少树的高度，提
    供更高效的搜索和插入操作。它保持了树的平衡性，且所有叶子节点都在同一层，
    这样可以保证较为平衡的查询性能。然而，2-3树的实现和维护操作较为复杂，
    导致其并不常用，更常见的是其变种B-树和B+树，它们在2-3树的基础上进行了
    一些优化和改进。

##### Java代码实现 #####

// 2-3树的节点类
    class Node {
        
        private int[] keys;  // 节点的关键字
        private Node[] children;  // 子节点数组
        private int size;  // 节点包含的关键字数量
        private boolean isLeaf;  // 是否为叶子节点
    
        public Node(boolean isLeaf) {
        
            this.keys = new int[3];
            this.children = new Node[4];
            this.size = 0;
            this.isLeaf = isLeaf;
        }
    
        // 从节点中查找关键字的位置
        public int findKey(int key) {
        
            for (int i = 0; i < size; i++) {
        
                if (keys[i] == key) {
        
                    return i;
                } else if (keys[i] > key) {
        
                    return -1;
                }
            }
            return -1;
        }
    
        // 在节点中插入关键字
        public void insertKey(int key) {
        
            if (size == 0) {
        
                keys[0] = key;
                size++;
            } else {
        
                int i = size - 1;
                while (i >= 0 && keys[i] > key) {
        
                    keys[i + 1] = keys[i];
                    i--;
                }
                keys[i + 1] = key;
                size++;
            }
        }
    
        // 在节点中删除关键字
        public void deleteKey(int key) {
        
            int index = findKey(key);
            if (index != -1) {
        
                for (int i = index; i < size - 1; i++) {
        
                    keys[i] = keys[i + 1];
                }
                size--;
            }
        }
    
        // 获取节点的关键字数量
        public int getSize() {
        
            return size;
        }
    
        // 判断节点是否为叶子节点
        public boolean isLeaf() {
        
            return isLeaf;
        }
    
        // 获取节点指定位置的子节点
        public Node getChild(int index) {
        
            return children[index];
        }
    
        // 设置节点指定位置的子节点
        public void setChild(int index, Node child) {
        
            children[index] = child;
        }
    }
    
    // 2-3树类
    class TwoThreeTree {
        
        private Node root;
    
        public TwoThreeTree() {
        
            root = null;
        }
    
        // 在2-3树中插入关键字
        public void insert(int key) {
        
            if (root == null) {
        
                root = new Node(true);
                root.insertKey(key);
            } else {
        
                Node newNode = insertKey(root, key);
                if (newNode != null) {
        
                    Node oldRoot = root;
                    root = new Node(false);
                    root.setChild(0, oldRoot);
                    root.setChild(1, newNode);
                    root.insertKey(newNode.keys[0]);
                    root.insertKey(oldRoot.keys[0]);
                }
            }
        }
    
        // 在给定的节点中插入关键字
        private Node insertKey(Node node, int key) {
        
            if (node.isLeaf()) {
        
                node.insertKey(key);
                if (node.getSize() > 2) {
        
                    return splitLeaf(node);
                }
            } else {
        
                int i = node.getSize() - 1;
                while (i >= 0 && key < node.getChild(i).keys[0]) {
        
                    i--;
                }
                Node newNode = insertKey(node.getChild(i + 1), key);
                if (newNode != null) {
        
                    node.insertKey(newNode.keys[0]);
    	}

#### B-树（B-tree） ####

B-树（B-tree）是一种平衡的多路查找树，广泛应用于在磁盘等外部存储设备中
    高效地存储和检索大量数据。以下是关于B-树的详细介绍：

![在这里插入图片描述][b1940beef5474ac1a138d0d2a19cc816.png]

##### 结构特点： #####

B-树由节点组成，每个节点可以存储多个
    关键字，这些关键字按升序排列。
    B-树的特点是节点的关键字按升序排列，具有高度平衡的特性。
    每个节点通常有多个子节点，最多可以拥有m个子节点，其中m称为B-树的阶数。

##### 插入操作： #####

1、当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
    2、如果节点已满，则需要进行节点分裂操作。将中间位置的关键字提升为父节
    	点，并将节点分裂为两个节点，将剩余的关键字均匀分配到这两个节点中。
    3、如果要插入的节点还没有满，则直接将关键字插入到合适的位置。

##### 删除操作： #####

1、当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
    2、如果该节点是叶子节点，直接删除关键字即可。如果该节点是内部节点，需
    	要找到其前驱或后继关键字来替代删除的关键字。
    3、在删除操作后，如果节点中的关键字数量过少，则需要进行节点合并或者从
    	兄弟节点中借用关键字来保持树的平衡。

##### 查询操作： #####

B-树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，
    向左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。

![在这里插入图片描述][69d822ab74e84793bf3ca38223b8aeb7.png]

##### 强调 #####

B-树适用于大规模数据存储和查询的场景，尤其是需要在外部存储设备上进行操
    作的情况。B-树的高度平衡保证了较为均衡的查询性能，因为从根节点到叶子节
    点的路径长度相等或差别不大。B-树的阶数m可以根据具体应用和硬件限制来选
    择，通常情况下，较大的阶数有助于减少磁盘访问的次数，提高效率。
    
    B-树的变种B+树在B-树的基础上做了一些优化，将所有数据存储在叶子节点中，
    使得范围查询和顺序访问更加高效。因此，在现代数据库系统和文件系统中，
    B+树更加常见和广泛应用。

##### 代码实现 #####

import java.util.ArrayList;
    import java.util.List;
    
    class BMinusTreeNode {
        
        public boolean isLeaf; // 是否是叶子节点
        public List<Integer> keys; // 节点中存储的关键字
        public List<BMinusTreeNode> children; // 节点的子节点
    
        public BMinusTreeNode() {
        
            keys = new ArrayList<>();
            children = new ArrayList<>();
        }
    }
    
    class BMinusTree {
        
        private BMinusTreeNode root;
        private int t; // B-树的阶数
    
        public BMinusTree(int degree) {
        
            root = new BMinusTreeNode();
            root.isLeaf = true;
            t = degree;
        }
    
        public void insert(int key) {
        
            // 根节点满了就分裂
            if (root.keys.size() == (2 * t)) {
        
                BMinusTreeNode newRoot = new BMinusTreeNode();
                newRoot.children.add(root);
                splitChild(newRoot, 0, root);
                root = newRoot;
            }
            insertNonFull(root, key);
        }
    
        private void insertNonFull(BMinusTreeNode node, int key) {
        
            int index = node.keys.size() - 1;
            if (node.isLeaf) {
        
                while (index >= 0 && node.keys.get(index) > key) {
        
                    index--;
                }
                node.keys.add(index + 1, key);
            } else {
        
                while (index >= 0 && node.keys.get(index) > key) {
        
                    index--;
                }
                index++;
                if (node.children.get(index).keys.size() == (2 * t)) {
        
                    splitChild(node, index, node.children.get(index));
                    if (node.keys.get(index) < key) {
        
                        index++;
                    }
                }
                insertNonFull(node.children.get(index), key);
            }
        }
    
        private void splitChild(BMinusTreeNode parent, int index, BMinusTreeNode node) {
        
            BMinusTreeNode newNode = new BMinusTreeNode();
            newNode.isLeaf = node.isLeaf;
            parent.keys.add(index, node.keys.get(t - 1));
            parent.children.add(index + 1, newNode);
            for (int i = t; i < 2 * t - 1; i++) {
        
                newNode.keys.add(node.keys.get(i));
            }
            if (!node.isLeaf) {
        
                for (int i = t; i < 2 * t; i++) {
        
                    newNode.children.add(node.children.get(i));
                }
            }
            for (int i = 2 * t - 2; i >= t - 1; i--) {
        
                node.keys.remove(i);
            }
            if (!node.isLeaf) {
        
                for (int i = 2 * t - 1; i >= t; i--) {
        
                    node.children.remove(i);
                }
            }
        }

#### B+树（B+tree） ####

B+树（B+ tree）是B-树的一种变种，特别适用于范围查询和顺序访问。

##### 结构特点： #####

B+树与B-树类似，由节点组成，每个节点可以存储多个关键字，这些关键字按升
    序排列。
    
    B+树的特点是只有叶子节点存储了真实数据，而内部节点仅用于索引。叶子节点
    通过指针连接形成一个链表，方便范围查询和顺序访问。

###### 内部节点特点： ######

内部节点存储关键字和指向子节点的指针。
    内部节点的关键字按升序排列，用于指示范围查询的起点。
    内部节点的指针指向比关键字更大的子节点。

###### 叶子节点特点： ######

叶子节点存储真实数据和指向下一个叶子节点的指针。
    叶子节点的关键字按升序排列，支持范围查询和顺序访问。
    所有叶子节点通过指针连接成一个链表，便于范围查询和顺序访问。

##### 插入操作： #####

当要插入一个关键字时，从根节点开始，找到合适的叶子节点。
    如果叶子节点已满，则需要进行节点分裂操作。将中间位置的关键字提升到父节
    点，并将两个剩余的部分分别创建为新的叶子节点。
    如果叶子节点还没有满，则直接将关键字插入到合适的位置。

##### 删除操作： #####

当要删除一个关键字时，从根节点开始，找到包含该关键字的叶子节点。
    直接删除叶子节点中的关键字，并更新链表指针。
    删除操作后，如果叶子节点的关键字个数过少，则需要从兄弟节点借用关键字或
    进行节点合并。

##### 查询操作： #####

B+树的查询操作与B-树类似，从根节点开始，根据关键字的大小比较，向左或向
    	右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。
    对于范围查询和顺序访问，可以从叶子节点开始，沿着链表进行遍历。

##### 强调 #####

B+树的特点在于只有叶子节点存储真实数据，这样使得范围查询和顺序访问更加
    高效，因为数据在叶子节点上连续存储，读取连续的数据块比随机读取更快。而
    内部节点仅存储索引信息，可以容纳更多的索引，提高了查询效率。B+树的实现
    适用于需要高效地处理大量数据的数据库和文件系统，能够提供较高的查询性能
    和存储效率。

##### 代码实现 #####

import java.util.ArrayList;
    import java.util.List;
    
    class BPlusTreeNode {
        
        public boolean isLeaf;
        public List<Integer> keys;
        public List<Object> values;
        public List<BPlusTreeNode> children;
        public BPlusTreeNode next;
    
        public BPlusTreeNode() {
        
            isLeaf = false;
            keys = new ArrayList<>();
            values = new ArrayList<>();
            children = new ArrayList<>();
            next = null;
        }
    }
    
    class BPlusTree {
        
        private BPlusTreeNode root;
        private int m;
    
        public BPlusTree(int m) {
        
            root = new BPlusTreeNode();
            root.isLeaf = true;
            this.m = m;
        }
    
        // 插入操作
        public void insert(int key, Object value) {
        
            if (root.keys.size() == m) {
        
                BPlusTreeNode newRoot = new BPlusTreeNode();
                newRoot.children.add(root);
                splitChild(newRoot, 0, root);
                root = newRoot;
            }
            insertNonFull(root, key, value);
        }
    
        // 非满子节点插入操作
        private void insertNonFull(BPlusTreeNode node, int key, Object value) {
        
            int index = node.keys.size() - 1;
            if (node.isLeaf) {
        
                while (index >= 0 && node.keys.get(index) > key) {
        
                    index--;
                }
                node.keys.add(index + 1, key);
                node.values.add(index + 1, value);
                node.next = node.next;
            } else {
        
                while (index >= 0 && node.keys.get(index) > key) {
        
                    index--;
                }
                index++;
                if (node.children.get(index).keys.size() == m) {
        
                    splitChild(node, index, node.children.get(index));
                    if (node.keys.get(index) < key) {
        
                        index++;
                    }
                }
                insertNonFull(node.children.get(index), key, value);
            }
        }
    
        // 分裂满子节点
        private void splitChild(BPlusTreeNode parent, int index, BPlusTreeNode node) {
        
            BPlusTreeNode newNode = new BPlusTreeNode();
            newNode.isLeaf = node.isLeaf;
            parent.keys.add(index, node.keys.get(m / 2));
            parent.children.add(index + 1, newNode);
    
            newNode.keys.addAll(node.keys.subList((m / 2) + 1, m));
            newNode.values.addAll(node.values.subList((m / 2) + 1, m));
            
            if (!node.isLeaf) {
        
                newNode.children.addAll(node.children.subList((m / 2) + 1, m + 1));
                node.children.subList((m / 2) + 1, m + 1).clear();
            } else {
        
                newNode.next = node.next;
                node.next = newNode;
            }
    
            node.keys.subList(m / 2, m).clear();
            node.values.subList(m / 2, m).clear();
        }
    
        // 搜索操作
        public List<Object> search(int key) {
        
            return search(root, key);
        }
    
        private List<Object> search(BPlusTreeNode node, int key) {
        
            int index = 0;
            while (index < node.keys.size() && key > node.keys.get(index)) {
        
                index++;
            }
            if (index < node.keys.size() && key == node.keys.get(index)) {
        
                return node.values.get(index);
            } else if (node.isLeaf) {
        
                return null;
            } else {
        
                return search(node.children.get(index), key);
            }
        }
    }

#### B树（B-tree） ####

B树（B-tree）是一种平衡的多路查找树，主要用于在磁盘等外部存储设备中高
    效地存储和检索大量数据。以下是关于B树的详细介绍：

##### 结构特点： #####

B树由节点组成，每个节点可以存储多个关键字，这些关键字按升序排列。
    B树的特点是节点的关键字按升序排列，具有高度平衡的特性。
    每个节点通常有多个子节点，最多可以拥有m个子节点，其中m称为B树的阶数。

##### 插入操作： #####

当要插入一个关键字时，从根节点开始，判断关键字应插入的位置。
    如果节点已满（即已有m-1个关键字），则需要进行节点分裂操作。将中间位置
    的关键字提升为父节点，并将节点分裂为两个节点，将剩余的关键字均匀分配到
    这两个节点中。
    如果要插入的节点还没有满，则直接将关键字插入到合适的位置。

##### 删除操作： #####

当要删除一个关键字时，从根节点开始，找到包含该关键字的节点。
    如果该节点是叶子节点，直接删除关键字。
    如果该节点是内部节点，有几种情况需要处理：
    如果该节点有足够多的关键字，则可以直接删除关键字。
    如果该节点的关键字数量过少，需要考虑兄弟节点的关键字数量以及兄弟节点合
    并的情况。

##### 查询操作： #####

B树的查询操作与二叉查找树类似，从根节点开始，根据关键字的大小比较，向
    左或向右子节点递归查询，直到找到匹配的关键字或遇到叶子节点。
    B树适用于大规模数据存储和查询的场景，特别适用于外部存储设备上的数据存
    储。其平衡性保证了较为均衡的查询性能，因为从根节点到叶子节点的路径长度
    相等或差别不大。B树的阶数m可以根据具体应用和硬件限制来选择，较大的阶数
    有助于减少磁盘访问的次数，提高效率。

##### 强调 #####

B树的变种B+树在B树的基础上做了一些优化，将所有的数据都存储在叶子节点
    中，使得范围查询和顺序访问更加高效。因此，B+树在现代数据库系统和文件
    系统中更为常见和广泛应用。、

##### 代码实现 #####

import java.util.ArrayList;
    import java.util.List;
    
    class BTreeNode {
        
        int degree; // B树的阶数
        List<Integer> keys; // 节点中存储的关键字
        List<BTreeNode> children; // 节点的子节点
        boolean isLeaf; // 是否是叶子节点
    
        public BTreeNode(int degree, boolean isLeaf) {
        
            this.degree = degree;
            this.isLeaf = isLeaf;
            keys = new ArrayList<>();
            children = new ArrayList<>();
        }
    }
    
    class BTree {
        
        BTreeNode root; // B树的根节点
        int degree; // B树的阶数
    
        public BTree(int degree) {
        
            this.degree = degree;
            root = new BTreeNode(degree, true);
        }
    
        // 插入关键字
        public void insert(int key) {
        
            if (root.keys.size() == (2 * degree - 1)) {
        
                BTreeNode newRoot = new BTreeNode(degree, false);
                newRoot.children.add(root);
                splitChild(newRoot, 0, root);
                root = newRoot;
            }
            insertNonFull(root, key);
        }
    
        // 在非满节点插入关键字
        private void insertNonFull(BTreeNode node, int key) {
        
            int index = node.keys.size() - 1;
            if (node.isLeaf) {
        
                while (index >= 0 && key < node.keys.get(index)) {
        
                    index--;
                }
                node.keys.add(index + 1, key);
            } else {
        
                while (index >= 0 && key < node.keys.get(index)) {
        
                    index--;
                }
                index++;
                if (node.children.get(index).keys.size() == (2 * degree - 1)) {
        
                    splitChild(node, index, node.children.get(index));
                    if (key > node.keys.get(index)) {
        
                        index++;
                    }
                }
                insertNonFull(node.children.get(index), key);
            }
        }
    
        // 分裂子节点
        private void splitChild(BTreeNode parent, int index, BTreeNode node) {
        
            BTreeNode newNode = new BTreeNode(degree, node.isLeaf);
            parent.keys.add(index, node.keys.get(degree - 1));
            parent.children.add(index + 1, newNode);
            for (int i = 0; i < degree - 1; i++) {
        
                newNode.keys.add(node.keys.get(i + degree));
                if (!node.isLeaf) {
        
                    newNode.children.add(node.children.get(i + degree));
                }
            }
            if (!node.isLeaf) {
        
                newNode.children.add(node.children.get(2 * degree - 1));
            }
            for (int i = degree - 1; i >= 0; i--) {
        
                node.keys.remove(i + degree - 1);
                if (!node.isLeaf) {
        
                    node.children.remove(i + degree);
                }
            }
        }
    
        // 搜索关键字
        public boolean search(int key) {
        
            return search(root, key);
        }
    
        private boolean search(BTreeNode node, int key) {
        
            int index = 0;
            while (index < node.keys.size() && key > node.keys.get(index)) {
        
                index++;
            }
            if (index < node.keys.size() && key == node.keys.get(index)) {
        
                return true;
            } else if (node.isLeaf) {
        
                return false;
            } else {
        
                return search(node.children.get(index), key);
            }
        }
    }

#### Trie树（字典树或前缀树） ####

Trie树，也被称为字典树或前缀树，是一种用于高效存储和搜索字符串的树型数
    据结构。Trie树的主要特点是通过字符串的前缀来进行搜索和匹配。

##### 结构特点： #####

Trie树由根节点和一系列子节点组成。
    根节点不包含任何关键字，每个子节点都表示一个字符，并按字符的顺序连接形
    成路径。
    从根节点到每个叶子节点的路径都对应一个字符串。
    每个节点可以存储额外的信息，如词频或附加数据等。

##### 插入操作： #####

当要插入一个字符串时，从根节点开始，逐个字符按顺序插入。
    如果某个字符对应的子节点不存在，则创建一个新的子节点。
    插入字符串的最后一个字符后，将当前节点标记为一个单词的结束。

##### 搜索操作： #####

当要搜索一个字符串时，从根节点开始，逐个字符按顺序匹配。
    如果某个字符对应的子节点存在，则继续匹配下一个字符。
    如果匹配遇到缺失的字符或到达某个节点后没有子节点，则表示字符串不在Trie
    树中。
    如果匹配成功并且在Trie树中找到最后一个字符，则表示字符串存在于Trie树中。

##### 删除操作： #####

当要删除一个字符串时，从根节点开始，逐个字符按顺序遍历。
    如果遍历过程中发现某个字符对应的子节点不存在，则表示字符串不存在于Trie
    树中。
    如果遍历成功，并到达字符串的最后一个字符，将当前节点的结束标记取消。
    如果遍历成功，但还存在其他相关字符串（例如，删除"abc"但还有"abcd"），
    可以保留当前节点以表示其他相关字符串。

##### 优点： #####

搜索的时间复杂度与字符串长度无关，仅与Trie树的高度相关，通常比哈希表更
    高效。
    可以高效地搜索具有相同前缀的字符串集合。
    对于字符串的前缀匹配和自动补全，Trie树可以提供高效的结果。

##### 缺点: #####

空间消耗较大，尤其在处理大量长字符串时。为了缓解这个问题，可以使用压缩
    的Trie树，如压缩前缀树（Patricia树）或Trie树的变种来减少存储空间。

##### 代码实现 #####

class TrieNode {
        
        private TrieNode[] children;
        private boolean isEndOfWord;
    
        public TrieNode() {
        
            children = new TrieNode[26]; // 26个英文字母
            isEndOfWord = false;
        }
    
        public TrieNode getChild(char ch) {
        
            return children[ch - 'a'];
        }
    
        public void setChild(char ch, TrieNode node) {
        
            children[ch - 'a'] = node;
        }
    
        public boolean isEndOfWord() {
        
            return isEndOfWord;
        }
    
        public void setEndOfWord(boolean isEndOfWord) {
        
            this.isEndOfWord = isEndOfWord;
        }
    }
    
    class Trie {
        
        private TrieNode root;
    
        public Trie() {
        
            root = new TrieNode();
        }
    
        public void insert(String word) {
        
            TrieNode node = root;
            for (char ch : word.toCharArray()) {
        
                if (node.getChild(ch) == null) {
        
                    node.setChild(ch, new TrieNode());
                }
                node = node.getChild(ch);
            }
            node.setEndOfWord(true);
        }
    
        public boolean search(String word) {
        
            TrieNode node = findNode(word);
            return node != null && node.isEndOfWord();
        }
    
        public boolean startsWith(String prefix) {
        
            TrieNode node = findNode(prefix);
            return node != null;
        }
    
        private TrieNode findNode(String str) {
        
            TrieNode node = root;
            for (char ch : str.toCharArray()) {
        
                node = node.getChild(ch);
                if (node == null) {
        
                    return null;
                }
            }
            return node;
        }
    }

使用示例

public class Main {
        
        public static void main(String[] args) {
        
            Trie trie = new Trie();
            trie.insert("apple");
            trie.insert("banana");
            trie.insert("grape");
            
            System.out.println(trie.search("apple")); // 输出: true
            System.out.println(trie.search("orange")); // 输出: false
            
            System.out.println(trie.startsWith("app")); // 输出: true
            System.out.println(trie.startsWith("ban")); // 输出: true
            System.out.println(trie.startsWith("grap")); // 输出: true
        }
    }

[40cdddf12c9b45b0bb965614e6171157.png]: https://img-blog.csdnimg.cn/40cdddf12c9b45b0bb965614e6171157.png
[2a437733152f49d4abfcc940cd2f91f2.png]: https://img-blog.csdnimg.cn/2a437733152f49d4abfcc940cd2f91f2.png
[dc77927a94d74f80b89752fee346fa0d.png]: https://img-blog.csdnimg.cn/dc77927a94d74f80b89752fee346fa0d.png
[b1940beef5474ac1a138d0d2a19cc816.png]: https://img-blog.csdnimg.cn/b1940beef5474ac1a138d0d2a19cc816.png
[69d822ab74e84793bf3ca38223b8aeb7.png]: https://img-blog.csdnimg.cn/69d822ab74e84793bf3ca38223b8aeb7.png