数据结构二

Leek posted @ 2010年5月27日 00:44 in 【算法学习】 with tags Coding 数据结构 , 1999 阅读

 关于平衡二叉树只会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;
    }
}

 

 

等有时间改成模板实现吧

 

CBSE Sample Paper 说:
2022年9月22日 02:06

All the Central Board of Secondary Education Students of Chennai Scheme, Delhi Scheme and All India Scheme can download the Sample Paper Suggestions with Model Papers along with Previous Years old Exam Solved Question Bank for all Languages & Subjects of the Course. CBSE Sample Paper All the Central Board of Secondary Education Students of Chennai Scheme, Delhi Scheme and All India Scheme can download the Sample Paper Suggestions with Model Papers along with Previous Years old Exam Solved Question Bank for all Languages & Subjects of the Course.

civaget 说:
2023年12月08日 05:24

Harness the power of 백링크 and transform your website's online presence. Building a strong network of backlinks from authoritative sources is a strategic move in the world of SEO.

civaget 说:
2023年12月13日 21:13

Embrace the power of 휴식, a lifeline to well-being, vitality, and a balanced life.

SEO 说:
2023年12月16日 21:33

Toto Match's 365-day verification ensures 메이저사이트 reliability. Bet with confidence, knowing your safety is guaranteed.

civaget 说:
2023年12月27日 20:49

epl무료중계: Where EPL passion meets unmatched insights.

civaget 说:
2023年12月29日 17:53

청주휴게텔 is my top choice for a spa day. Can't wait to book my appointment and escape the daily grind.

civaget 说:
2023年12月31日 22:43

I'm a loyal customer of 포항오피 for its quality services.

civaget 说:
2024年1月01日 22:28

강남출장마사지 - a holistic approach to health and relaxation.

pavzi.com 说:
2024年1月22日 15:26

Pavzi.com provides all the news about Gadgets, the Economy, Technology, Business, Finance and many more. The main concept or our aim behind this website has been the will to provide resources with full information on each topic which can be accessed through the Internet. To ensure that every reader gets what is important and worthy about the topic they search and link to hear from us. pavzi.com Our site is a multiple Niche or category website which will ensure to provide information and resources on each and every topic. Some of the evergreen topics you will see on our website are Career, Job Recruitment, Educational, Technology, Reviews and others. We are targeting mostly so it is true that Tech, Finance, and Product Reviews. The only reason we have started this website is to make this site the need for your daily search use.


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter