无极app定制开发公司网站模板,办公室装修设计效果图大全,怎样做网商网站,中国数控机床网多路查找树
多路查找树#xff08;Multway Search Tree#xff09;是一种高级的树形数据结构#xff0c;它
允许每个节点有多个子节点#xff08;通常大于等于2#xff09;。多路查找树的每个节点
可以存储多个关键字和对应的值。分类
2-3树#xff08;2-3 Tree#x…多路查找树
多路查找树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树是一种
有效的数据结构。详细介绍 2-3树2-3 Tree
2-3树是一种平衡的多路查找树每个节点可以存储1个或2个关键字并有2个
或3个子节点。以下是关于2-3树的详细介绍结构特点
2-3树由节点组成每个节点可以存储1个或2个关键字这些关键字按升序排列。
每个节点有2个或3个子节点对应于存储的关键字个数。
所有叶子节点都在同一层且根节点到每个叶子节点的路径长度相等保持树的
平衡性。插入操作
1、当要插入一个关键字时从根节点开始判断关键字应插入的位置。
2、如果节点已满即已有两个关键字则需要进行节点分裂操作。将中间较大的关键字移动到上一层的父节点并将两个剩余的关键字分别创建为新的子节点。
3、如果节点还没有满则直接将关键字插入到正确的位置。删除操作
当要删除一个关键字时从根节点开始找到包含该关键字的节点。如果该节点是叶子节点直接删除关键字即可。如果该节点是内部节点有几种情况需要处理如果该节点有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-树的详细介绍结构特点
B-树由节点组成每个节点可以存储多个
关键字这些关键字按升序排列。
B-树的特点是节点的关键字按升序排列具有高度平衡的特性。
每个节点通常有多个子节点最多可以拥有m个子节点其中m称为B-树的阶数。插入操作
1、当要插入一个关键字时从根节点开始判断关键字应插入的位置。
2、如果节点已满则需要进行节点分裂操作。将中间位置的关键字提升为父节点并将节点分裂为两个节点将剩余的关键字均匀分配到这两个节点中。
3、如果要插入的节点还没有满则直接将关键字插入到合适的位置。删除操作
1、当要删除一个关键字时从根节点开始找到包含该关键字的节点。
2、如果该节点是叶子节点直接删除关键字即可。如果该节点是内部节点需要找到其前驱或后继关键字来替代删除的关键字。
3、在删除操作后如果节点中的关键字数量过少则需要进行节点合并或者从兄弟节点中借用关键字来保持树的平衡。查询操作
B-树的查询操作与二叉查找树类似从根节点开始根据关键字的大小比较
向左或向右子节点递归查询直到找到匹配的关键字或遇到叶子节点。强调
B-树适用于大规模数据存储和查询的场景尤其是需要在外部存储设备上进行操
作的情况。B-树的高度平衡保证了较为均衡的查询性能因为从根节点到叶子节
点的路径长度相等或差别不大。B-树的阶数m可以根据具体应用和硬件限制来选
择通常情况下较大的阶数有助于减少磁盘访问的次数提高效率。B-树的变种B树在B-树的基础上做了一些优化将所有数据存储在叶子节点中
使得范围查询和顺序访问更加高效。因此在现代数据库系统和文件系统中
B树更加常见和广泛应用。代码实现
import java.util.ArrayList;
import java.util.List;class BMinusTreeNode {public boolean isLeaf; // 是否是叶子节点public ListInteger keys; // 节点中存储的关键字public ListBMinusTreeNode 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树Btree
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 ListInteger keys;public ListObject values;public ListBPlusTreeNode 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 ListObject search(int key) {return search(root, key);}private ListObject 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树的阶数ListInteger keys; // 节点中存储的关键字ListBTreeNode 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)); // 输出: trueSystem.out.println(trie.search(orange)); // 输出: falseSystem.out.println(trie.startsWith(app)); // 输出: trueSystem.out.println(trie.startsWith(ban)); // 输出: trueSystem.out.println(trie.startsWith(grap)); // 输出: true}
}
