/*
* SBTree.h
*
* Created on: 2013-5-2
* Author: Random
*/
#ifndef SBTREE_H_
#define SBTREE_H_
#include <iostream>
namespace random{
typedef struct _NoneType {} NoneType;
template <typename KEY, typename VALUE = NoneType>
struct SBNodeBase
{
SBNodeBase(): size(0){}
unsigned int size;
KEY key;
VALUE value;
};
template <typename KEY, typename VALUE = NoneType>
struct SBNode:public SBNodeBase<KEY, VALUE>
{
SBNode():SBNodeBase<KEY, VALUE>(), left(0), right(0){}
SBNode* left;
SBNode* right;
};
template <typename KEY, typename VALUE = NoneType>
class SBTree
{
public:
typedef const SBNodeBase<KEY, VALUE>* const NodeType;
SBTree():m_root(0){}
~SBTree();
public:
// 插入键值key
void Insert(const KEY& key, const VALUE value = NoneType());
// 删除键值key
bool Delete(const KEY& key);
bool Delete(NodeType pNode);
// 树中键值< v的结点数
unsigned int Rank(const KEY& key);
// 树中键值大于或等于key的结点数
unsigned int LastRank(const KEY& key);
// 查找第一个值为key的节点
NodeType Find(const KEY& key);
// 查找个数
unsigned int FindCnt(const KEY& key);
// 清理
void Clear();
// 最小的头
NodeType Head();
// 最大的尾
NodeType End();
// 根
NodeType Root(){return this->m_root;}
// 比key小的最大节点
NodeType Pred(const KEY& key);
// 比key大的最小节点
NodeType Succ(const KEY& key);
// 选择排名为k的节点
NodeType operator [](unsigned int uIndex);
// 删除根
void PopRoot();
// 删除头
void PopHead();
// 删除尾
void PopEnd();
// 获取size
unsigned int Size(){ if(this->m_root) return this->m_root->size; return 0;}
// 打印使用
void Print();
void Print(const SBNode<KEY, VALUE>* pNode, unsigned short uHeight = 0, bool isLeft = true);
private:
void clear_node(SBNode<KEY, VALUE>* pNode);
void left_rotate(SBNode<KEY, VALUE>*& pNode);
void right_rotate(SBNode<KEY, VALUE>*& pNode);
void main_tain(SBNode<KEY, VALUE>*& pNode, bool isRightDeeper);
int unsigned short _S(SBNode<KEY, VALUE>* pNode){if (pNode) return pNode->size; return 0;}
void sbt_insert(SBNode<KEY, VALUE>*& pT, SBNode<KEY, VALUE>* pNode);
SBNode<KEY, VALUE>* sbt_delete(SBNode<KEY, VALUE>*& pNode, const KEY& key, bool isFind);
unsigned int sbt_rank(SBNode<KEY, VALUE>* pNode, const KEY& key);
SBNode<KEY, VALUE>* sbt_find(SBNode<KEY, VALUE>* pNode, const KEY& key);
unsigned int sbt_find_cnt(SBNode<KEY, VALUE>* pNode, const KEY& key);
SBNode<KEY, VALUE>* sbt_pop_head(SBNode<KEY, VALUE>*& pNode);
SBNode<KEY, VALUE>* sbt_pop_end(SBNode<KEY, VALUE>*& pNode);
private:
SBNode<KEY, VALUE>* m_root;
};
template <typename KEY, typename VALUE>
SBTree<KEY, VALUE>::~SBTree()
{
Clear();
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::Clear()
{
this->clear_node(this->m_root);
this->m_root = 0;
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::clear_node(SBNode<KEY, VALUE>* pNode)
{
if (!pNode)
{
return;
}
this->clear_node(pNode->left);
this->clear_node(pNode->right);
delete pNode;
pNode = 0;
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::left_rotate(SBNode<KEY, VALUE>*& pNode)
{
SBNode<KEY, VALUE>* pRight = pNode->right;
pNode->right = pRight->left;
pRight->left = pNode;
pRight->size = pNode->size;
pNode->size = this->_S(pNode->left) + this->_S(pNode->right) + 1;
pNode = pRight;
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::right_rotate(SBNode<KEY, VALUE>*& pNode)
{
SBNode<KEY, VALUE>* pLeft = pNode->left;
pNode->left = pLeft->right;
pLeft->right = pNode;
pLeft->size = pNode->size;
pNode->size = this->_S(pNode->left) + this->_S(pNode->right) + 1;
pNode = pLeft;
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::main_tain(SBNode<KEY, VALUE>*& pNode, bool isRightDeeper)
{
if (!pNode)
{
return;
}
if(!isRightDeeper)
{
if (!pNode->left) return;
unsigned int uRSize = this->_S(pNode->right);
if (this->_S(pNode->left->left) > uRSize)
{
this->right_rotate(pNode);
}
else if(this->_S(pNode->left->right) > uRSize)
{
this->left_rotate(pNode->left);
this->right_rotate(pNode);
}
else
{
return;
}
this->main_tain(pNode->left, false);
}
else
{
if (!pNode->right) return;
unsigned int uLSize = this->_S(pNode->left);
if (this->_S(pNode->right->right) > uLSize)
{
this->left_rotate(pNode);
}
else if(this->_S(pNode->right->left) > uLSize)
{
this->right_rotate(pNode->right);
this->left_rotate(pNode);
}
else
{
return;
}
this->main_tain(pNode->right, true);
}
this->main_tain(pNode, false);
this->main_tain(pNode, true);
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::Insert(const KEY& key, const VALUE value)
{
SBNode<KEY, VALUE>* pNode = new SBNode<KEY, VALUE>();
pNode->key = key;
pNode->value = value;
this->sbt_insert(this->m_root, pNode);
}
template <typename KEY, typename VALUE>
void SBTree<KEY, VALUE>::sbt_insert(SBNode<KEY, VALUE>*& pT, SBNode<KEY, VALUE>* pNode)
{
if(!pT)
{
pNode->size = 1;
pT = pNode;
return;
}
++pT->size;
bool isLeft = pNode->key < pT->key;
if(isLeft)
{
this->sbt_insert(pT->left, pNode);
}
else
{
this->sbt_insert(pT->right, pNode);
}
this->main_tain(pT, !isLeft);
}
// 删除键值key
template <typename KEY, typename VALUE>
bool SBTree<KEY, VALUE>::Delete(const KEY& key)
{
SBNode<KEY, VALUE>* pNode = this->sbt_delete(this->m_root, key, false);
if (pNode)
{
delete pNode;
return true;
}
return false;
}
template <typename KEY, typename VALUE>
bool SBTree<KEY, VALUE>::Delete(typename SBTree<KEY, VALUE>::NodeType pNode)
{
if (!pNode)
{
return false;
}
return this->Delete(pNode->key);
}
template <typename KEY, typename VALUE>
SBNode<KEY, VALUE>* SBTree<KEY, VALUE>::sbt_delete(SBNode<KEY, VALUE>*& pNode, const KEY& key, bool isFind)
{
// 查找到key所在的节点，然后用该节点左子树中最大值节点来替换掉需要删除的节点
if(!pNode)
{
return 0;
}
SBNode<KEY, VALUE>* pRecord;
pRecord = 0;
// 只支持每次删除掉一个节点
if (isFind && !pNode->right)
{
// 查找最右的子树中最右的节点来替代删除的节点
pRecord = pNode;
pNode = pNode->left;
return pRecord;
}
if(!isFind && key == pNode->key)
{
// 如果查询到是相等的节点
if(pNode->size == 1)
{
// 叶子节点，需要删除掉此节点
pRecord = pNode;
pNode = 0;
return pRecord;
}
if (pNode->size == 2)
{
// 单枝节点，需要子节点继承被删除的节点
pRecord = pNode->left?pNode->left:pNode->right;
pNode->left = 0;
pNode->right = 0;
}
else
{
// 当前节点的左子树的最大值作为pNode的代替节点
pRecord = this->sbt_delete(pNode->left, key, true);
}
if (pRecord)
{
pNode->key = pRecord->key;
pNode->value = pRecord->value;
}
-- pNode->size;
this->main_tain(pNode, true);
}
else if(!isFind && key < pNode->key )
{
pRecord = this->sbt_delete(pNode->left, key, false);
if(pRecord)
{
-- pNode->size;
}
}
else
{
pRecord = this->sbt_delete(pNode->right, key, isFind);
if(pRecord)
{
-- pNode->size;
}
}
this->main_tain(pNode, !isFind && key < pNode->key);
return pRecord;
}
template <typename KEY, typename VALUE>
unsigned int SBTree<KEY, VALUE>::Rank(const KEY& key)
{
return this->sbt_rank(this->m_root, key);
}
template <typename KEY, typename VALUE>
unsigned int SBTree<KEY, VALUE>::sbt_rank(SBNode<KEY, VALUE>* pNode, const KEY& key)
{
if(!pNode)
{
ret
