构造N个节点的所有HB(k)树(广义AVL树)实现

回顾一下HB(k)树的定义:

HB(k)树要么是空树要么是满足如下条件的二叉搜索树:

其左右子树均为HB(k)树,且右子树高度和左子树高度差的绝对值小于等于k.

现在给定从小到大排序的N个关键码,现要构造出这些关键码对应的所有HB(k)树,算法如下(C++实现)

#include <iostream>
#include <vector>
#include <utility>
#include <algorithm>
#include <memory>
#include <stack>
#include <map>
using namespace std;

const long long k = 2;
template <typename T>
struct HB_kTreeNode  //AVL树节点类
{
	long long bf;  //节点平衡因子
	T data;  //节点数据域
	HB_kTreeNode* left;
	HB_kTreeNode* right;
	HB_kTreeNode(long long b, const T& d) :bf(b), data(d), left(nullptr), right(nullptr) {}
	HB_kTreeNode(const HB_kTreeNode& copy) :bf(copy.bf), data(copy.data), left(nullptr), right(nullptr) {}
	HB_kTreeNode(const T& d) :data(d), left(nullptr), right(nullptr) {}
};

template <typename T>
bool CompareHB_KTree(HB_kTreeNode<T> *root1, HB_kTreeNode<T>* root2)
{
	if (root1 != nullptr || root2 != nullptr)
	{
		if (root1 == nullptr || root2 == nullptr)
			return false;
		if (root1->data != root2->data)
			return false;
		if (CompareHB_KTree(root1->left, root2->left) && CompareHB_KTree(root1->right, root2->right))
			return true;
		return false;
	}
	return true;
}

struct record
{
	size_t left;   //HB(k)树对应的关键码序列起始点下标
	size_t right;  //HB(k)树对应的关键码序列终止点下标
	long long H;   //HB(k)树高度
	record(size_t l, size_t r, long long H) :left(l), right(r), H(H) {}
	bool operator<(const record& r) const
	{
		if (left < r.left)
			return true;
		if (left > r.left)
			return false;
		if (right < r.right)
			return true;
		if (right > r.right)
			return false;
		if (H < r.H)
			return true;
		if (H > r.H)
			return false;
		return false;
	}
};

template<typename T>
HB_kTreeNode<T>* copyTree(HB_kTreeNode<T>* root)
{
	if (root == nullptr)
		return nullptr;
	HB_kTreeNode<T>* _new = new HB_kTreeNode<T>(*root);
	_new->left = copyTree(root->left);
	_new->right = copyTree(root->right);
	return _new;
}

pair<size_t, size_t> getIntersection(pair<size_t, size_t> l, pair<size_t, size_t> j) //返回区间l,j的交区间,l,g左右端点均为正整数,返回(0,0)表示交集不存在
{
	if (l.second < j.first || l.first > j.second)
		return { 0 , 0 };
	if (j.first <= l.first)
	{
		if (j.second < l.second)
			return {l.first, j.second};
		return l;
	}

	if (j.second <= l.second)
		return j;
	return { j.first, l.second };
}

template <typename T>
size_t select(size_t value, const vector<T>& key_seq)
{
	if (value > key_seq.size())
		return key_seq.size();
	return value;
}

size_t select(size_t end, size_t max)
{
	if (end <= max)
		return 0;
	return end - max;
}

template <typename T>
void constructHB_kTree(long long H, const vector<T> &key_seq, size_t start, size_t end, vector<HB_kTreeNode<T> *> &result, const vector<size_t> &Nh_max, const vector<size_t> &Nh_min,
   map<record, shared_ptr<vector<HB_kTreeNode<T>*>>> &has_computed)
{
	if (H == 0)  //高度为0,无树
	{
		result.push_back(nullptr);
		return;
	}
	long long K = min(H - 1, k);
	if (K != 0)
	{                                   //start + Nh_max[H - 1] >= end - Nh_max[H - 1]总为真,因为调用函数时高为H的HBk树总存在
		pair<size_t, size_t> cur;
		long long i = K;
		while ((cur = getIntersection(make_pair(start + Nh_min[H - 1 - i], select(start + Nh_max[H - 1 - i], key_seq)), make_pair(select(end, Nh_max[H - 1]), end - Nh_min[H - 1]))) == pair<size_t, size_t>(0, 0))
		{
			--i;
		}
		//循环结束后i>=0总成立理由同上
		pair<size_t, size_t> cur_symmetric(end + start - cur.second, end + start - cur.first);

		size_t left_start = cur.first - 1;
		cur.first = 0;
		cur.second -= left_start + 1;
		vector<shared_ptr<vector<HB_kTreeNode<T>*>>> left(cur.second + 1, nullptr);
		size_t right_start = cur_symmetric.second - 1;
		cur_symmetric.first = cur_symmetric.second - cur_symmetric.first;
		cur_symmetric.second = 0;
		size_t pos_right_most = cur.second;
		vector<shared_ptr<vector<HB_kTreeNode<T>*>>> right(cur_symmetric.first + 1, nullptr);

		for (; i > 0; --i)  //i == K处理完后退出
		{
			processLeft(left_start, i, H, cur, key_seq, start, end, Nh_max, Nh_min, left, result, has_computed);  //处理左子树
			processRight(right_start, i, H, cur_symmetric, key_seq, start, end, Nh_max, Nh_min, right, result, has_computed);  //处理右子树

			pair<size_t, size_t> after = getIntersection(make_pair(start + Nh_min[H - i], select(start + Nh_max[H - i], key_seq)), make_pair(select(end, Nh_max[H - 1]), end - Nh_min[H - 1]));
			if (after == pair<size_t, size_t>(0, 0))
				break;

			cur_symmetric.first = right_start - (end + start - after.second) + 1;
			cur_symmetric.second = right_start - (end + start - after.first) + 1;

			after.first -= left_start + 1;
			after.second -= left_start + 1;
            
			if (after.second > pos_right_most)
			{
				left.resize(after.second + 1, nullptr);
				pos_right_most = after.second;
				right.resize(cur_symmetric.first + 1, nullptr);
			}
			cur = after;
		}

		if (i == 0)
			processWhenBfEqualZero(right_start, left_start, H, cur, key_seq, start, end, Nh_max, Nh_min, left, right, result, has_computed);   //处理左右子树高度相等的情形
	}
	else
	{
		result.push_back(new HB_kTreeNode<T>(0, key_seq[start - 1]));
	}
}

enum class flag { left_visited, right_visited, non_visited };
template <typename T>
void constructSubTree (size_t offset, long long bf, const shared_ptr<vector<HB_kTreeNode<T>*>> &left_result, const shared_ptr<vector<HB_kTreeNode<T>*>>& right_result, const vector<T>& key_seq, vector<HB_kTreeNode<T>*>& result, bool left_visited, bool right_visited)
{
	for (size_t j = 0; j < left_result->size(); ++j)
	{
		for (size_t m = 0; m < right_result->size(); ++m)
		{
			HB_kTreeNode<T>* root = new HB_kTreeNode<T>(bf, key_seq[offset]);
			if (!left_visited && m == 0)
				root->left = (*left_result)[j];
			else
				root->left = copyTree((*left_result)[j]);

			if (!right_visited && j == 0)
				root->right = (*right_result)[m];
			else
				root->right = copyTree((*right_result)[m]);
			result.push_back(root);
		}
	}
}

template <typename T>
bool avoidCall(map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed, long long H, size_t start, size_t end, shared_ptr<vector<HB_kTreeNode<T>*>> &result,
	const vector<T>& key_seq, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min)
{
	auto t = has_computed.find(record(start, end, H - 1));
	if (t != has_computed.end())
	{ 
		result = t->second;
		return true;
	}
	else
	{
		constructHB_kTree(H - 1, key_seq, start, end, *result, Nh_max, Nh_min, has_computed);
		has_computed.insert(make_pair(record(start, end, H - 1), result));
		return false;
	}
}
template <typename T>
void processWhenBfEqualZero(size_t right_start, size_t left_start, long long H, const pair<size_t, size_t>& cur, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
	vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& left, vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& right, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
	for (size_t run = cur.first; run <= cur.second; ++run)
	{
		shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
		shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();

		bool left_visited;
		if (right[right_start- run -left_start] == nullptr)
		{
			left_visited = avoidCall(has_computed, H, start, run + left_start, left_result, key_seq, Nh_max, Nh_min);
			right[right_start - run - left_start] = left_result;
		}
		else
		{
			left_visited = true;
			left_result = right[right_start - run - left_start];
		}
			
		bool right_visited;
		if (left[run] == nullptr)
		{
			right_visited = avoidCall(has_computed, H, run + left_start + 2, end, right_result, key_seq, Nh_max, Nh_min);
			left[run] = right_result;		
		}
		else
		{
			right_result = left[run];
			right_visited = true;
		}
			
		constructSubTree(run + left_start, 0, left_result, right_result, key_seq, result, left_visited, right_visited);
	}
}

template <typename T>
void processLeft(size_t left_start, const long long& i, long long H, const pair<size_t, size_t>& cur, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
	vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& left, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
	for (size_t run = cur.first; run <= cur.second; ++run)
	{
		shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
		shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();
	
		bool left_visited;
		left_visited = avoidCall(has_computed, H - i, start, run + left_start, left_result, key_seq, Nh_max, Nh_min);
	
		bool right_visited;
		if (left[run] == nullptr)
		{
			right_visited = avoidCall(has_computed, H, run + left_start + 2, end, right_result, key_seq, Nh_max, Nh_min);
			left[run] = right_result;
		}
		else
		{
			right_result = left[run];
			right_visited = true;
		}
		constructSubTree(left_start + run, i, left_result, right_result, key_seq, result, left_visited, right_visited);
	}
}

template <typename T>
void processRight(size_t right_start, const long long& i, long long H, const pair<size_t, size_t>& cur_symmetric, const vector<T>& key_seq, size_t start, size_t end, const vector<size_t>& Nh_max, const vector<size_t>& Nh_min,
	vector<shared_ptr<vector<HB_kTreeNode<T>*>>>& right, vector<HB_kTreeNode<T>*>& result, map<record, shared_ptr<vector<HB_kTreeNode<T>*>>>& has_computed)
{
	for (size_t run = cur_symmetric.second; run <= cur_symmetric.first; ++run)
	{
		shared_ptr<vector<HB_kTreeNode<T>*>> left_result = make_shared<vector<HB_kTreeNode<T>*>>();
		shared_ptr<vector<HB_kTreeNode<T>*>> right_result = make_shared<vector<HB_kTreeNode<T>*>>();
		bool left_visited;

		if (right[run] == nullptr)   //子树未求出,递归调用求子树
		{
			left_visited = avoidCall(has_computed, H, start, right_start - run, left_result, key_seq, Nh_max, Nh_min);
			right[run] = left_result;
		}
		else
		{
			left_visited = true;   //子树已求出,直接使用现成结果
			left_result = right[run];
		}

		bool right_visited;
		right_visited = avoidCall(has_computed, H - i, right_start - run + 2, end, right_result, key_seq, Nh_max, Nh_min);
		constructSubTree(right_start - run, -i, left_result, right_result, key_seq, result, left_visited, right_visited);
	}
}

template <typename T>
int Searchd(HB_kTreeNode<T>* ptr, int d)
{
	if (d == 2)
		return 0;
	else
	{
		if (d == 1)
		{
			if (ptr->right == nullptr)
				return 0;
			else
				return 2;
		}
		else
		{
			if (ptr->left != nullptr)
				return 1;
			else
			{
				if (ptr->right != nullptr)
					return 2;
				else
					return 0;
			}
		}
	}
}

template <typename T>
bool isHBTree(HB_kTreeNode<T> *root)  //判断以root为根节点的二叉树是否为AVL树
{
	struct memory
	{
		HB_kTreeNode<T>* p;
		int direction;
		T lmin;
		int lh = 0;   //节点左子树高度
		memory(HB_kTreeNode<T>* p, int d) :p(p), direction(d) {}
	};
	T rmin;
	T rmax;
	T lmax;
	int rh;
	int d = 0;
	HB_kTreeNode<T>* ptr = root;
	HB_kTreeNode<T>* const dest = ptr;
	stack<memory> arrange;
	bool TF = false;
	while (true)
	{
		if (Searchd(ptr, d) == 0)
		{
			if (ptr == dest)
			{
				if (d == 0)
					return true;
			}

			if (d == 0)
			{
				if (arrange.top().direction == 1)
				{
					arrange.top().lh = 1;
					arrange.top().lmin = ptr->data;
					lmax = ptr->data;
				}
				else
				{
					rh = 1;
					rmin = ptr->data;
					rmax = ptr->data;
				}
			}
			else
			{
				if (d == 1)
				{
					if (lmax >= ptr->data)
					{
						cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
						return false;
					}

					if (arrange.top().lh > k)
					{
						cout << "存在左右子树高度差绝对值大于" << k << "的子树,原树非HB(" << k << ")树" << endl;
						return false;
					}

					if (ptr == dest)
						return true;

					T lmin = arrange.top().lmin;
					int lh = arrange.top().lh;
					arrange.pop();
					if (arrange.top().direction == 1)
					{
						arrange.top().lmin = lmin;
						arrange.top().lh = lh + 1;
						lmax = ptr->data;
					}
					else
					{
						rmin = lmin;
						rmax = ptr->data;
						rh = lh + 1;
					}

				}
				else
				{
					if (rmin <= ptr->data)
					{
						cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
						return false;
					}

					if (abs(rh - arrange.top().lh) > k)
					{
						cout << "存在左右子树高度差绝对值大于" << k << "的子树,原树非HB(" << k << ")树" << endl;
						return false;
					}

					if (ptr == dest)
						return true;

					if (ptr->left == nullptr)
					{
						arrange.pop();
						if (arrange.top().direction == 1)
						{
							arrange.top().lmin = ptr->data;
							lmax = rmax;
							arrange.top().lh = rh + 1;
						}
						else
						{
							rmin = ptr->data;
							++rh;
						}
					}
					else
					{
						T lmin = arrange.top().lmin;
						int lh = arrange.top().lh;
						arrange.pop();
						if (arrange.top().direction == 1)
						{
							arrange.top().lmin = lmin;
							arrange.top().lh = max(lh, rh) + 1;
							lmax = rmax;
						}
						else
						{
							rmin = lmin;
							rh = max(lh, rh) + 1;
						}
					}
				}
			}
			ptr = arrange.top().p;
			d = arrange.top().direction;
		}
		else
		{
			HB_kTreeNode<T>* interval = nullptr;
			if (d == 0)
			{
				arrange.push(memory(ptr, Searchd(ptr, d)));
				if (arrange.top().direction == 1)
					ptr = ptr->left;
				else
					ptr = ptr->right;
			}
			else
			{
				if (ptr->data <= lmax)
				{
					cout << "当前树非二叉搜索树,也非HB(" << k << ")树" << endl;
					return false;
				}
				arrange.top().direction = 2;
				ptr = ptr->right;
			}
			d = 0;
		}
	}
}

template <typename T>
void delHB_kTree(HB_kTreeNode<T>* root)
{
	if (root == nullptr)
		return;
	delHB_kTree(root->left);
	delHB_kTree(root->right);
	delete root;
}

/*template <typename T>
shared_ptr<vector<HB_kTreeNode<T>*>> constructBinaryTree(vector<T>& inorder_traversal, size_t left_index, size_t right_index)
{
	if (left_index > right_index)  //二叉树为空树,直接返回空根节点
	{
		return make_shared<vector<HB_kTreeNode<T>*>>(1, nullptr);
	}

	shared_ptr<vector<HB_kTreeNode<T>*>> root_node_list = make_shared<vector<HB_kTreeNode<T>*>>();  //当前中序序列对应的所有二叉树的根节点表
	for (size_t i = left_index - 1; i < right_index; ++i)
	{
		shared_ptr<vector<HB_kTreeNode<T>*>> left_sub(constructBinaryTree(inorder_traversal, left_index, i));  //构造所有左子树
		shared_ptr<vector<HB_kTreeNode<T>*>> right_sub(constructBinaryTree(inorder_traversal, i + 2, right_index));  //构造所有右子树
		for (size_t j = 0; j < left_sub->size(); ++j)
		{
			for (size_t k = 0; k < right_sub->size(); ++k)  //由构造出的左右子树合成当前中序序列对应的所有二叉树
			{
				HB_kTreeNode<T>* root = new HB_kTreeNode<T>(inorder_traversal[i]);
				if (k == 0)
					root->left = (*left_sub)[j];
				else
					root->left = copyTree((*left_sub)[j]);

				if (j == 0)
					root->right= (*right_sub)[k];
				else
					root->right = copyTree((*right_sub)[k]);
				root_node_list->push_back(root);
			}
		}
	}

	return root_node_list;
}*/

int main()
{
	const size_t N = 10;   //节点数目
	vector<size_t> Nh_max(1, 0);   //各指定高度的HB(k)树最大节点数
	vector<size_t> Nh_min(1, 0);    //各指定高度的HB(k)树最小节点数
	vector<int> key_seq(N);    //关键码序列
	vector<HB_kTreeNode<int>*> result;   //构造结果

	for (size_t i = 0; i < N; ++i)
	{
		key_seq[i] = i + 1;
	}

	map<record, shared_ptr<vector<HB_kTreeNode<int>*>>> has_computed;
	while (true)
	{
		if (Nh_min.back() <= key_seq.size() && key_seq.size() <= Nh_max.back())  //节点数在最大数最小数之间,对应的HB(k)树存在,执行构造算法
		{
			constructHB_kTree(Nh_min.size() - 1, key_seq, 1, key_seq.size(), result, Nh_max, Nh_min, has_computed);
		}

		if (k > Nh_min.size() - 1)
			Nh_min.push_back(Nh_min.back() + 1);
		else
			Nh_min.push_back(Nh_min[Nh_min.size() - 1 - k] + Nh_min.back() + 1);

		if (key_seq.size() < Nh_min.back())  //节点数小于最小节点数,此后HB(k)树不存在,结束构造
			break;
		else
			Nh_max.push_back(2 * Nh_max.back() + 1);
	}

	cout << "共生成了" << result.size() << "棵HB(" << k << ")树"<< endl;
	/*shared_ptr<vector<HB_kTreeNode<int>*>> r = constructBinaryTree(key_seq, 1, N);
	size_t count = 0;
	for (HB_kTreeNode<int>*& go : *r)
	{
		if (isHBTree(go))
		{
			++count;
		}
	}

	cout << "一共有" << count << "棵HB树" << endl;

	/*for (size_t i = 0; i < result.size(); ++i)
	{
		if (isHBTree(result[i]) == false)
		{
			cout << "错误!生成结果中存在非HB(" << k << ")树" << endl;
			exit(-1);
		}
	}

	for (size_t i = 0; i < result.size() - 1; ++i)
	{
		for (size_t j = i + 1; j < result.size(); ++j)
		{
			if (CompareHB_KTree(result[i], result[j]))
			{
				cout << "错误生成的HB树中存在相等的一对HB树!" << endl;
				exit(-1);
			}
		}
	}
	cout << "生成结果正确!" << endl;
	for (size_t i = 0; i < result.size(); ++i)
	{
		delHB_kTree(result[i]);
	}
	cout << "销毁成功!" << endl;   //需要比较一下树是否两两不同 */
    return 0;
}

N=10显示共有732棵HB(k)树(使用以上代码中的输入数据)

上一篇:数表查找之平衡二叉树


下一篇:二叉搜索树的理解以及AVL树的模拟实现