基数树算法原理和实现程序

基数树（Radix Tree，也称为Trie树或前缀树），是一种用于存储字符串的数据结构，它的核心思想是利用字符串的位（数字）信息来组织节点。每个节点代表一个字符串的前缀，从根到叶节点的路径对应了一个完整的字符串。基数树的主要特点是对关键字进行分段比较，并沿着相应路径向下查找，支持高效的前缀匹配和插入/删除操作。

算法原理：
1. **基本结构**：基数树的每个节点包含一个字符数组（通常是大小为基数的数组，比如10进制的基数树用数组长度为10），用于存储该节点下的子节点位置，以及一个表示是否到达叶子节点的标志。
2. **构建过程**：当新字符串插入时，从根开始遍历，遇到的每一个字符都会确定一个子节点的位置，如果没有对应位置，则新建子节点。如果字符串结束，那么对应的叶子节点标记为已存在。
3. **查询操作**：查找时，从根开始，按字符顺序依次检查节点，直到找到完全匹配的字符串，或者到达空节点（不存在该前缀）。

下面是一个简单的Python实现示例，使用字典来模拟一个二进制基数树（即ASCII码为基础）：

class Node:
    def __init__(self):
        self.children = [None] * 256
        self.is_end = False

class RadixTree:
    def __init__(self):
        self.root = Node()

    def insert(self, word):
        current = self.root
        for char in word:
            if not current.children[ord(char)]:
                current.children[ord(char)] = Node()
            current = current.children[ord(char)]
        current.is_end = True

    def search(self, word):
        current = self.root
        for char in word:
            if not current.children[ord(char)]:
                return None
            current = current.children[ord(char)]
        return current is not None and current.is_end

# 使用示例
rt = RadixTree()
rt.insert("apple")
print(rt.search("app"))  # 输出True，因为app是apple的前缀
print(rt.search("banana"))  # 输出False