【数据结构】竞赛树 | LOUIS' BLOG

[isLouisHsu]

https://louishsu.xyz/2020/03/06/%E3%80%90%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%91%E7%AB%9E%E8%B5%9B%E6%A0%91/

定义及概念定义：竞赛树(tournament tree)也是完全二叉树，它的基本操作是替换最大(或最小)元素。如果有$n$个元素，这个基本操作的用时为$\Theta(\log n)$。 竞赛树可分为赢者树(winner tree)和输者树(loser tree)，每个内部节点分别记录比赛的赢者和输者。在最小赢者树(min winner tree)中，分数小的选手获胜，分数相等则左孩子获胜，最大赢者