数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究数据结构中的锦标赛树、获胜树和失败树
在这里，我们将了解锦标赛树、获胜树和失败树。锦标赛树是一个完全二叉树，它有 n 个外部节点和 n - 1 个内部节点。外部节点代表选手，内部节点代表两名选手比赛的获胜者。这棵树也被称为选择树。
锦标赛树有一些特性。如下所示：
这棵树是根节点的。因此，树中的链接和从父节点到子节点的有向路径，并且有一个唯一的元素没有父节点。
父节点的值小于或等于该节点，对于任何比较运算符，只要父节点和子节点的相对值在整棵树中保持不变，就可以使用。
节点数不是 2 的幂的树包含空洞。空洞可以出现在树中的任何位置。
这棵树是二叉堆的适当泛化。
根节点将代表锦标赛的整体获胜者。
锦标赛树有两种类型：
获胜树
失败树
获胜树
获胜树是一个完全二叉树，其中每个节点都代表其两个子节点中较小或较大的节点，称为获胜树。根节点保存树中最小的或最大的节点。锦标赛树的获胜者是在所有序列中第 n 个最小或最大的键。很容易看出，获胜树可以在 O(log n) 时间内形成。
**示例** - 假设有一些键，3、5、6、7、20、8、2、9。
失败树
失败树是针对 n 个选手的完全二叉树，其中存在 n 个外部节点和 n - 1 个内部节点。比赛的失败者存储在内部节点中。但在此整体获胜者存储在 tree[0] 中。失败者是一种替代表示，它在相应的节点存储比赛的失败者。失败者的一个优点是，在输出获胜树后重构树，只需要检查从叶子到根节点路径上的节点，而不是该路径上节点的兄弟节点。
**示例** - 要形成失败树，我们必须首先创建获胜树。
假设有一些键，10、2、7、6、5、9、12、1。因此，我们将首先创建最小获胜树。
现在，我们将每个内部节点中比赛的失败者存储起来。
更新于：2020 年 8 月 11 日
6K+ 次查看
广告