时间戳

首页 > 解决方案 > 在没有适当索引的数据树中查询的最有效方法

node.js - 在没有适当索引的数据树中查询的最有效方法

问题描述

如果标题的术语有误，请原谅我。让我说明一下我的意思：

我有一个基础教育课程的数据树。每个节点都有 2 个值（除了子数据和父数据）：ID 和一个布尔值。我无法更改 ID 值，因为我是从 API 获取它，所以我无法将我的数据树形成为二叉树。这就是我所说的“没有适当的索引”。顺便说一句：ID是随机的。

在此处输入图像描述

如您所见，我正在用层次结构构建我的树。课程是剧集的超集，剧集是主题的超集。

我的问题：

我想从特定主题节点收集一些数据。我知道它是一个主题节点并且我知道它的 ID。如何找到该节点以最有效地从中获取一些数据？

当我研究树数据结构时，他们通常用某种规则（例如：二叉树）索引他们的节点，我不确定我能做到这一点，因为我想保留数据类型的层次结构。如果有一种方法，我既可以保留某种层次结构的指示，又可以为许多有效查询排序我的树。我很高兴这样做。如果可能的话，我不想蛮力

标签： node.jsalgorithmsortingdata-structurestree

解决方案

您可以将通常的 Node 类方法与您在树实例级别维护的字典相结合。

例如：

class Node:
    def __init__(self, id, name, boolval):
        self.id = id
        self.name = name 
        self.boolval = boolval
        self.children = []
    
    def tolist(self):  # utility method for simple visualisation
        if not self.children:
            return [self.name]
        else:
            return [self.name, [child.tolist() for child in self.children]]

class Tree:
    def __init__(self):
        self.dict = dict()  # this will map id to node
        self.root = None
    
    def append(self, id, name, boolval, parentid=""):
        node = Node(id, name, boolval)
        self.dict[id] = node
        if self.root:
            parent = self.get(parentid)
            parent.children.append(node)
        else:
            self.root = node
        
    def get(self, id):
        return self.dict[id]

    def tolist(self):
        if not self.root:
            return
        return self.root.tolist()


# demo use:
tree = Tree()
tree.append("ab12", "Tree", False)
tree.append("ab13", "Physics", False, "ab12")
tree.append("a4d5", "Math", False, "ab12")
tree.append("524d", "Section A", False, "a4d5")
# ...etc

print(tree.tolist())

如果您需要从给定节点知道其层次结构是什么，则添加父引用：

class Node:
    def __init__(self, id, name, boolval):
        self.id = id
        self.name = name 
        self.boolval = boolval
        self.children = []
        self.parent = None

    def path(self):
        if self.parent:
            return self.parent.path() + [self.id]
        return [self.id] 

    def tolist(self):  # utility method for simple visualisation
        if not self.children:
            return [self.name]
        else:
            return [self.name, [child.tolist() for child in self.children]]

class Tree:
    def __init__(self):
        self.dict = dict()  # this will map id to node
        self.root = None
    
    def append(self, id, name, boolval, parentid=""):
        node = Node(id, name, boolval)
        self.dict[id] = node
        if self.root:
            parent = self.get(parentid)
            parent.children.append(node)
            node.parent = parent
        else:
            self.root = node
        
    def get(self, id):
        return self.dict[id]

    def tolist(self):
        if not self.root:
            return
        return self.root.tolist()


# demo use:
tree = Tree()
tree.append("ab12", "Tree", False)
tree.append("ab13", "Physics", False, "ab12")
tree.append("a4d5", "Math", False, "ab12")
tree.append("524d", "Section A", False, "a4d5")
# ...etc

print(tree.tolist())
print(tree.get("524d").path())  # ['ab12', 'a4d5', '524d']

推荐阅读