binarytree.cpp

组播密钥的批次更新算法

#include "node.h"
#include "binarytree.h"
#include ".\binarytree.h"

int max(int a,int b)
{
	return (a>b ? a : b);
}
CBinaryTree::CBinaryTree(void)
: m_root(0)
{
}

CBinaryTree::~CBinaryTree(void)
{
	DestroySubTree(m_root);
}

void CBinaryTree::DestroySubTree(CNode* &subroot)
{
	if (subroot==0)
		return;

	this->DestroySubTree(subroot->m_leftchild);
	this->DestroySubTree(subroot->m_rightchild);
	
	delete subroot;
	subroot=0;
}

CNode* CBinaryTree::GetNode(int nodeID)
{
	return GetNode(m_root,nodeID);
}

CNode* CBinaryTree::GetNode(CNode* subRoot, int nodeID)
{
	if(subRoot!=0)
	{
		if(subRoot->m_nodeID==nodeID)
			return subRoot;
		else
		{
			CNode* leftSearchResult=GetNode(subRoot->m_leftchild,nodeID);
			if(leftSearchResult!=0)
				return leftSearchResult;
			else 
				return GetNode(subRoot->m_rightchild,nodeID);
		}
	}
	return 0;
}

int CBinaryTree::GetHeight(void)
{
	return GetSubHeight(m_root);
}

int CBinaryTree::GetSubHeight(CNode* subRoot)
{
	if(subRoot==0)
		return 0;
	else
		return 1+max(GetSubHeight(subRoot->m_leftchild),GetSubHeight(subRoot->m_rightchild));
}

CNode* CBinaryTree::AddNewLeaf()
{
	CNode* leaffound=m_root;
	while(leaffound!=0 && (leaffound->m_leftchild!=0 || leaffound->m_rightchild!=0))
	{
		//左子树高于右子树，向右子树中插入
		if(leaffound->m_sign > 0)	
			leaffound=leaffound->m_rightchild;
		else
			leaffound=leaffound->m_leftchild;
	}

	//如果循环因为subRoot==0而终止则说明根
	//节点现在为空新建节点就是所谓的根节点
	if(leaffound==0)
	{
		m_root=new CNode();
		m_root->m_nodeID=GetNewID();
		return m_root;
	}
	else
	{	//找到了合适的插入位置
		
		//首先考虑根节点情况
		if(leaffound==this->m_root)
		{
			//另创建一个节点作为新的根节点,左孩子为原根节点,右孩子为新插入节点
			CNode* midNode=new CNode();
			CNode* newNode=new CNode();

			midNode->m_nodeID=GetNewID();
			newNode->m_nodeID=GetNewID();

			m_root=midNode;
			m_root->SetLeftChild(leaffound);
			m_root->SetRightChild(newNode);
			return newNode;
		}
		else
		{
			//另创建一个节点在该位置充当中间节点,其右孩子为找到的叶子节点,左孩子为新插入节点
            CNode* parent=leaffound->m_parent;
			CNode* midNode=new CNode();
			CNode* newNode=new CNode();
			
			midNode->m_nodeID=GetNewID();
			newNode->m_nodeID=GetNewID();
			
			//若找到位置是某节点的左孩子则
			//将新建中间节点设置为其左孩子
			if(parent->m_leftchild==leaffound)
				parent->SetLeftChild(midNode);
			else
				parent->SetRightChild(midNode);
			
			midNode->SetLeftChild(leaffound);
			midNode->SetRightChild(newNode);
			
			//更新新加入节点所有祖先节点的左右子树高度差
			UpdateSignsAfterInsertion(midNode);

			return newNode;
		}
	}
	return 0;
}

void CBinaryTree::UpdateSignsAfterInsertion(CNode* leafInserted)
{
	while(leafInserted!=0 && leafInserted->m_parent!=0)
	{
		//若新加入的叶子节点是某个节点的左孩子,则增加其父亲节
		//点的左子树的高度.反之则增加其父亲节点的右子树的高度
		if(leafInserted==leafInserted->m_parent->m_leftchild)
		{
			leafInserted->m_parent->m_sign++;
		}
		else
		{
			leafInserted->m_parent->m_sign--;
		}

		leafInserted=leafInserted->m_parent;
	}
}


bool CBinaryTree::RemoveExistedLeaf(CNode* leafToRemove)
{
	if (leafToRemove!=0 && leafToRemove->m_rightchild==0 && leafToRemove->m_leftchild==0)
	{
		//如果欲删除节点是根节点
		if(leafToRemove==m_root)
		{
			this->m_root=0;
			delete leafToRemove;
		}
		else
		{
			CNode* parent=leafToRemove->m_parent;
			CNode* theSibling=leafToRemove->GetSibling();

			if(parent->m_parent==0)
			{
				//从逻辑上此时parent应是m_root
				this->m_root=theSibling;
				theSibling->m_parent=0;
			}
			else
			{
				//如果parent是某个节点的左孩子,则用leafToRemove兄弟节点取代parent的位置
				if(parent==parent->m_parent->m_leftchild)
					parent->m_parent->SetLeftChild(theSibling);
				else
					parent->m_parent->SetRightChild(theSibling);

				//子树高度减少
				UpdateSignsAfterDeletion(theSibling);
			}

			//删除中间节点,并将欲移除的节点与该树断绝关系
			delete parent;
			leafToRemove->m_parent=0;

			//删除欲移除的叶子节点
			delete leafToRemove;
		}
		return true;
	}
	return false;
}
int CBinaryTree::GetNewID(void)
{
	static int idCounter=0;
	return idCounter++;
}

void CBinaryTree::UpdateSignsAfterDeletion(CNode* leafDelete)
{
	while(leafDelete!=0 && leafDelete->m_parent!=0)
	{
		//若新加入的叶子节点是某个节点的左孩子,则增加其父亲节
		//点的左子树的高度.反之则增加其父亲节点的右子树的高度
		if(leafDelete==leafDelete->m_parent->m_leftchild)
		{
			leafDelete->m_parent->m_sign--;
		}
		else
		{
			leafDelete->m_parent->m_sign++;
		}

		leafDelete=leafDelete->m_parent;
	}
}