如何基于属性搜索以随机ID为键的二叉搜索树（BST）？

我要实现二叉搜索树（BST）的搜索功能，树的节点用随机生成的数字作为key，节点值是包含多个属性的Item对象。按key搜索BST很简单，能根据key的大小关系左右遍历，但按属性（比如标题）搜索时，似乎只能线性遍历所有节点找匹配项，这好像违背了BST的设计初衷。想知道怎么实现搜索标题为“A Book”的节点，目前没找到可行思路。

import random

class Item:
    def __init__(self, title, category, language, authors, year_published):
        self.title = title
        self.category = category
        self.language = language
        self.authors = authors
        self.year_published = year_published
        self.id = random.randint(100000, 999999)

class Node:
    def __init__(self, item):
        self.left = None
        self.right = None
        self.key = item.id
        self.value = item

    def insert(self, item):
        if item.id < self.key:
            if self.left is None:
                self.left = Node(item)
                self.left.value = item
            else:
                self.left.insert(item)
        else:
            if self.right is None:
                self.right = Node(item)
                self.right.value = item
            else:
                self.right.insert(item)

    def find(self, key):
        if key < self.key:
            if self.left is None:
                return None
            else:
                return self.left.find(key)
        elif key > self.key:
            if self.right is None:
                return None
            else:
                return self.right.find(key)
        else:
            return self

def main():
    metamorphosis = Item("Metamorphosis", "Novel", 'English', 'Franz Kafka',1915)
    a_book = Item("A Book", "Biography", 'English', 'Someone',2024)
    journal = Item("A Journal", "Fiction", 'Various', 'Author',2001)

    library_tree = Node(metamorphosis)
    library_tree.insert(a_book)
    library_tree.insert(journal)

    # 想要实现的功能
    library_tree.search_title("A Book")

方法1：线性遍历所有节点 #

这是最直接的实现方式，虽然无法利用BST的有序性，但能快速满足需求。通过递归遍历整棵树的所有节点，逐一检查标题是否匹配。

给Node类添加search_title方法：

def search_title(self, target_title):
    # 检查当前节点
    if self.value.title == target_title:
        return self
    # 递归搜索左子树
    left_result = self.left.search_title(target_title) if self.left else None
    if left_result:
        return left_result
    # 递归搜索右子树
    right_result = self.right.search_title(target_title) if self.right else None
    return right_result

如果需要返回所有匹配标题的节点（比如存在同名书籍），可以修改为收集结果的版本：

def search_title(self, target_title, results=None):
    if results is None:
        results = []
    if self.value.title == target_title:
        results.append(self)
    if self.left:
        self.left.search_title(target_title, results)
    if self.right:
        self.right.search_title(target_title, results)
    return results

方法2：构建辅助索引字典 #

为了保留BST按key搜索的高效性，同时实现按标题快速查找，可以维护一个额外的字典，将标题映射到对应的Item ID（或直接映射到Node）。这样按标题搜索时，先查字典拿到ID，再用BST的find方法查找，时间复杂度为O(1)+O(log n)。

修改main函数添加索引逻辑：

def main():
    metamorphosis = Item("Metamorphosis", "Novel", 'English', 'Franz Kafka', 1915)
    a_book = Item("A Book", "Biography", 'English', 'Someone', 2024)
    journal = Item("A Journal", "Fiction", 'Various', 'Author', 2001)

    library_tree = Node(metamorphosis)
    # 构建标题到ID的索引字典
    title_to_id = {
        metamorphosis.title: metamorphosis.id,
        a_book.title: a_book.id,
        journal.title: journal.id
    }

    library_tree.insert(a_book)
    library_tree.insert(journal)

    # 按标题搜索的逻辑
    target_title = "A Book"
    if target_title in title_to_id:
        target_node = library_tree.find(title_to_id[target_title])
        print(target_node.value.title)  # 输出"A Book"
    else:
        print("未找到匹配标题的节点")

如果有动态插入新节点的需求，需要在insert方法中同步更新这个索引字典，比如给Node类添加索引参数，或者维护一个全局/类级别的索引。

方法3：构建多属性排序的BST（或其他数据结构） #

如果需要频繁按多个属性搜索，可以考虑构建多棵BST，每棵树按不同属性（比如标题、出版年份）作为key排序。但这种方式会增加插入和维护的复杂度，因为每次插入新节点都要在所有BST中插入一次。

也可以改用更适合多维度搜索的数据结构，比如红黑树、哈希表结合BST，但这已经超出了基础BST的范畴。

内容的提问来源于stack exchange，提问作者rgs