从链表创建索引树（平衡BST
我有一个双链表，我想从它创建一个索引树，以提高随机访问性能。链表中的节点没有唯一标识，可以是派生节点对象的任何实例，该对象具有next和previous引用。为了提高对节点的随机访问性能（即对列表的特定索引的访问），我想在列表的顶部添加一个索引树。例如，用户可能希望检索列表的第三个节点，然后检索第五个节点。我想知道对这个问题是否已经提出了任何解决办法。
我脑海中的一个解决方案是使用一种特殊类型的二叉树，其中每个节点保留一个数字。这个数字将显示它的子引用中保留了多少节点。例如，如果根节点的编号是5，这意味着列表有5个节点。假设左侧节点的编号是3，右侧节点的编号是2，这意味着前3个节点在左侧部分，其余2个在右侧部分。这将继续到叶子，叶子将有编号1，它将指向列表的节点。所需的树是一个平衡的BST。
另一种方法是将列表中节点的索引视为其数据（因此对其进行排序），并使用类似将排序列表转换为平衡的二叉搜索树的方法。此外，在树节点中添加对实际列表节点的引用，这样编号（数据）为2的节点将引用列表中的第二个节点。我想知道从一个链表创建和维护这棵树的最快方法是什么？
事先谢谢你
编辑：由于内存问题和持久性要求，我必须使用链接列表，而不仅仅是引用的数组。这一部分已经完成了，所以考虑一个从头部开始的链表。此外，您还可以访问列表中项目的尾部和数量。
共有1个答案
有一个简单的答案：指向列表中节点的指针数组。要获得第三个节点，只需索引数组中的第三个元素。如果您这样做，您将不再需要您的节点中的上一个和下一个成员；只需转到数组的前一个或下一个元素。
如果您还想维护一个动态链表，只需使用一个list
-
我不知道这些节点是否被插入，但输出结果是正确的。我只想插入节点到左边的孩子，我可以消除那代码吗？root.right=insertLevelOrder（arr,root.right,2*i+2)； 还有为什么这个循环没有“i++”的符号，int i是如何自动增加的？
-
我正在解决“破解编码面试”中的以下问题：实现一个函数来检查二叉树是否平衡。平衡树是这样一种树：任何节点的两个子树的高度相差不会超过一个。 这本书的示例解决方案（复制如下）假设从节点发出的树是平衡的，如果（a）节点的左子树和右子树是平衡的；和（b）节点本身是平衡的。我在试图理解为什么会这样？以上两个条件的满足如何证明从节点发出的整个树是平衡的？ 谢啦
-
在上一节中，我们考虑构建一个二叉搜索树。正如我们所学到的，二叉搜索树的性能可以降级到 $$O(n)$$ 的操作，如 get 和 put ，如果树变得不平衡。在本节中，我们将讨论一种特殊类型的二叉搜索树，它自动确保树始终保持平衡。这棵树被称为 AVL树，以其发明人命名：G.M. Adelson-Velskii 和E.M.Landis。 AVL树实现 Map 抽象数据类型就像一个常规的二叉搜索树，唯一
-
在我们继续之前，我们来看看执行这个新的平衡因子要求的结果。我们的主张是，通过确保树总是具有 -1,0或1 的平衡因子，我们可以获得更好的操作性能的关键操作。 让我们开始思考这种平衡条件如何改变最坏情况的树。有两种可能性，一个左重树和一个右重树。 如果我们考虑高度0,1,2和3的树，Figure 2 展示了在新规则下可能的最不平衡的左重树。 Figure 2 看树中节点的总数，我们看到对于高度为0的
-
问题内容： 我有对象T的列表，它具有父属性，其中顶级对象的父属性为null。我想将所有对象放入TreeSet（或TreeMap）中。顶级对象将是所有没有父级的根对象（父级为null），并且它们的下级将是其子级。 像这样 所以我可以得到Ra并找到它的子代（Ca1，Ca2，Ca11，Ca12…。） 更新：很抱歉，可能不清楚，节点指向父节点，如果parent为null，则它们是根节点。问题是父母需要了解
-
问题内容： 我正在为面向iPhone的站点在烧瓶中构建基本的CMS，但在某些方面遇到了一些麻烦。我有一个非常小的数据库，只有1个表（页面）。这是模型： 如您所见，对于子页面，它们仅引用字段中的另一个页面对象。我要在管理面板中执行的操作是将所有页面嵌套在其父页面中的嵌套无序列表。我对如何执行此操作几乎一无所知。我所能想到的是以下内容（只能正常工作（也许- 我尚未测试过）2级）： 然后，我将其格式化为