关于平衡二叉树只会AVL和傻X树：（   由于AVL各方面都不如SBT  所以只整理SBT算了。

        但是杯具的是把以前整理写的代码等Ctrl+A Shift+Delete了...

这个是模仿别人的重新写一个，其中删除是最有技巧结合平衡操作很精妙

/****************************************
*                 SBT.h
*		Describe: SBT平衡二叉树
*       Created: 2010-5-26
*       CopyRight  2010,Leek
*
******************************************/

#include <iostream>

using namespace std;

typedef int Type;

//	SBT存储结构
class SBTNode
{
public:
	SBTNode *child[2];
	SBTNode *parent;
	Type key;
	int size;
	SBTNode (Type key,int size);
};

typedef SBTNode *SBTree;

enum {Left,Right=1};

SBTNode::SBTNode (Type key,int size)
{
	this->key = key;
	this->size = size;
	child[Left] = child[Right] = parent = NULL;
}

void SBT_Rotate (SBTree &root, bool num)
{
	//num == Left 右旋num == Right左旋
	SBTNode *tmp = root->child[!num];
	tmp->parent = root->parent;
	if (tmp->child[num] != NULL)
		tmp->child[num]->parent = root;
	root->child[!num] = tmp->child[num];
	tmp->child[num] = root;

	tmp->size = root->size;
	root->size = root->child[Left]->size + root->child[Right]->size + Right;
	root = tmp;
}

void SBT_Maintain (SBTree &root, bool num)
{
	//人字型数据退化，但是其他数据速度都快
	if (root->child[num]->child[num]->size > root->child[!num]->size)
		SBT_Rotate (root, !num);
}

void SBT_Insert (SBTree &root, SBTNode *x)
{
	if (root == NULL)
		root = x;
	else
	{
		root->size++;
		x->parent = root;
		SBT_Insert (root->child[x->key > root->key], x);
		SBT_Maintain (root, x->key > root->key);
	}
}

SBTNode *SBT_Search (SBTree &root,Type key)
{
	return root == NULL || root->key == key? root: SBT_Search (root->child[key > root->key], key);
}

SBTNode *SBT_Delete (SBTree &root, Type key)
{
	if (root == NULL)
		return NULL;
	root->size--;
	if (root->key == key || root->child[key > root->key] == NULL)
	{
		SBTNode *tmp;
		if (root->child[Left] == NULL || root->child[Right] ==NULL)
		{
			tmp = root;
			root = root->child[root->child[Left] == NULL];
			if (root != NULL)
				root->parent = tmp->parent;
		}
		else
		{
			tmp = SBT_Delete (root->child[Right], key - Right);
			root->key = tmp->key;
		}
		return tmp;
	}
	else
		return SBT_Delete (root->child[key > root->key], key);
}

SBTNode *SBT_Pred(SBTree root, Type key)
{
    if (root == NULL)
		return NULL;
    if(key <= root->key)
		return SBT_Pred(root->child[Left],key);
    else
	{
        SBTNode *tmp=SBT_Pred(root->child[Right],key);
        return tmp != NULL?tmp:root;
    }
}

SBTNode *SBT_Succ (SBTree &root,Type key)
{
	if (root == NULL)
		return NULL;
	if (key >= root->key)
		return SBT_Succ(root->child[Right],key);
	SBTNode *tmp = SBT_Succ(root->child[Left], key);
	return tmp != NULL? tmp:root;
}

SBTNode *SBT_Select(SBTree root, int i)
{
    int r = root->child[Left]->size+Right;
    if (i == r)
		return root;
    else
		return SBT_Select(root->child[i>r],i>r?i-r:i);
}

int SBT_Rank(SBTree root, Type key)
{
    if (root == NULL)
		return Left;
    if (root->key == key)
		return root->child[Left]->size+Right;
    else
		if(key < root->key) 
			return SBT_Rank(root->child[Left],key);
    else
	{
        int r = SBT_Rank(root->child[Right],key);
        return r == Left? Left: r + root->child[Left]->size + Right;
    }
}

等有时间改成模板实现吧

• 相关文章