数据结构、算法与应用 13.3 赢者树

数据结构、算法与应用 13.3 赢者树

winnerTree.h

#ifndef WINNERTREE_H
#define WINNERTREE_H

template
class winnerTree
{
public:
	virtual ~winnerTree() {}
	virtual void initialize(T *thePlayer, int theNumberOfPlayers) = 0;
		// 用数组 thePlayer[1:numberOfPlayers] 生成赢者树
	virtual int winner() const = 0;
		// 返回赢者树的索引
	virtual void rePlay(int thePlayer) = 0;
		// 在参赛者 thePlayer 的分数变化后重赛
};

#endif // !WINNERTREE_H

completeWinnerTree.h

#ifndef COMPLELEWINNERTREE_H
#define COMPLELEWINNERTREE_H

#include "winnerTree.h"
#include "myExceptions.h"

template
class completeWinnerTree : public winnerTree
{
public:
	completeWinnerTree(T *thePlayer, int theNumberOfPlayers)
	{
		tree = nullptr;
		initialize(thePlayer, theNumberOfPlayers);
	}
	~completeWinnerTree() {delete [] tree;}
	void initialize(T*, int) override;
	int winner() const override {return tree[1];}
		// 返回赢者树的索引
	int winner(int i) const {return (i < numberOfPlayers) ? tree[i] : 0;}
		// 在节点i返回比赛的获胜者
	void rePlay(int) override;
		// 在参赛者 thePlater 的分数变化后重赛
	void output() const;
private:
	int lowExt;              // 最底层外部节点个数
	int offset;              // offset = 2^log(n - 1) - 1   n : 外部节点个数  s : 最底层最左端内部节点编号
	int *tree;               // 赢者树数组
	int numberOfPlayers;
	T *player;               // 参赛者(外部节点)
	void play(int, int, int);
};

template
void completeWinnerTree::initialize(T *thePlayer, int theNumberOfPlaters)
{// 为玩家创建赢者树 [1:NumberOfPlayer]
	int n = theNumberOfPlaters;
	if (n < 2)
		throw illegalParameterValue("必须至少有2名球员");

	player = thePlayer;
	numberOfPlayers = n;
	delete [] tree;
	tree = new int [n];

	// 计算 s = 2^log(n-1)
	int i, s;
	for (s = 1; 2 * s <= n; s += s);

	lowExt = 2 * (n - s);
	offset = 2 * s - 1;

	// 进行最低级别外部节点的匹配
	for (i = 2; i <= lowExt; i += 2)
		play((offset + i) / 2, i - 1, i);

	// 处理剩余的外部节点
	if (n % 2 == 1)
	{// 奇数 n，play 特殊的内部节点和外部节点
		play(n / 2, tree[n - 1], lowExt + 1);
		i = lowExt + 3;
	}
	else i = lowExt + 2;

	// i 是剩余最左侧的外部节点
	for (; i <= n; i += 2)
		play((i - lowExt + n - 1) / 2, i - 1, i);
}

template
void completeWinnerTree::play(int p, int leftChild, int rightChild)
{// 从树开始进行比赛 [p]
 // leftChild 是 p 的左子树
 // rightChild 是 p 的右子树
	tree[p] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild;

	// 如果在正确的子级，可能会有更多匹配
	while (p % 2 == 1 && p > 1)
	{// 正确的孩子
		tree[p / 2] = (player[tree[p - 1]] <= player[tree[p]]) ? tree[p - 1] : tree[p];
		p /= 2;   // 去找家长
	}
}

template
void completeWinnerTree::rePlay(int thePlayer)
{// 在参赛者 thePlayer 的分数变化后重赛
	int n = numberOfPlayers;
	if (thePlayer <= 0 || thePlayer > n)
		throw illegalParameterValue("玩家索引是非法的");

	int matchNode,        // 要进行下一场比赛的节点
		leftChild,        // 匹配节点的左子节点
		rightChild;       // 匹配节点的右子节点

	// 查找第一个匹配节点及其子节点
	if (thePlayer <= lowExt)
	{// 从最底层开始
		matchNode = (offset + thePlayer) / 2;
		leftChild = 2 * matchNode - offset;
		rightChild = leftChild + 1;
	}
	else
	{
		matchNode = (thePlayer - lowExt + n - 1) / 2;
		if (2 * matchNode == n - 1)
		{
			leftChild = tree[2 * matchNode];
			rightChild = thePlayer;
		}
		else
		{
			leftChild = 2 * matchNode - n + 1 + lowExt;
			rightChild = leftChild + 1;
		}
	}

	tree[matchNode] = (player[leftChild] <= player[rightChild]) ? leftChild : rightChild;

	// 第二场比赛的特例
	if (matchNode == n - 1 && n % 2 == 1)
	{
		matchNode /= 2;       // 移到父级
		tree[matchNode] = (player[tree[n - 1]] <= player[lowExt + 1]) ? tree [n - 1] : lowExt + 1;
	}

	// 打剩下的比赛
	matchNode /= 2;     // 移到父级
	for (; matchNode >= 1; matchNode /= 2)
		tree[matchNode] = (player[tree[2 * matchNode]] <= player[tree[2 * matchNode + 1]]) ? 
						   tree[2 * matchNode] : tree[2 * matchNode + 1];
}

template
void completeWinnerTree::output() const
{
	cout << "参赛人数  = " << numberOfPlayers
		<< " lowExt = " << lowExt
        << " offset = " << offset << endl;
	cout << "完成的优胜者树指针是" << endl;
	for (int i = 1; i < numberOfPlayers; i++)
		cout << tree[i] << ' ';
	cout << endl;
}

#endif // !COMPLELEWINNERTREE_H

方法 winner 的时间复杂性是 O(1)，initialize 的时间复杂性是 O(n)，rePlay 的时间复杂性是 O(logn)，其中 n 是选手个数。类的构造函数利用储存在数组中的选手进行赢者树的初始化。它的复杂性是 O(n)。