binary-search-tree - 为什么我们需要为红黑树中的每个节点存储一个父指针?
问题描述
红黑树是维护有序集合的有效数据结构。但是,我看到的所有实现(例如 c++ STL 或“算法简介”一书)似乎都为每个节点存储了一个父指针。这将导致更大的内存成本。
我认为可以删除这样的父指针。除了内存问题,我们不需要管理每个节点的父指针。然后每个节点只存储左子指针、右子指针、键和颜色。如果没有父指针,插入和删除仍然可以使用额外的堆栈来实现。
对于给定的键 $x$,我们首先从根开始并找到 $x$。通过这个过程,我们使用堆栈来记录路径上的所有节点。之后,如果我们需要旋转某个节点,可以使用堆栈查找父亲信息。它仍然很有效,每次操作的时间复杂度仍然是 O(log n)。
所以我不知道为什么当前的实现都在每个节点中存储父指针。
解决方案
拥有父指针使某些操作更容易实现,最值得注意的是从树的给定元素移动到下一个或前一个项目。如果每个节点都有父指针,则可以简单地实现这些操作,而无需每次都定位从根到当前项目的路径。
推荐阅读
- python - 如何使用原始 SQL 查询实现搜索功能
- redux - BotFramework WebChat - 示例 #14 - Redux 商店的中间件?
- c - How to fix &localtime in .txt - C
- mysql - Mysql 在任何数据库表上更新或插入时触发
- c++ - 如何修复 C++ 中的 Typedef 变量未识别错误(Visual Studio 2017)
- python - discord.ext.commands.errors.CommandInvokeError:命令引发异常:AttributeError:'utility'对象没有属性'channel'
- java - 如何捕获通过分布式系统中各个组件的事件的时间延迟?
- python - 将日期时间索引旋转到开始和结束列
- javascript - React 功能组件 - 直接访问 DOM 元素与通过 useRef
- python - How can I split up operands but keep the options together, in a wrapper script?