顺序统计树_用按层次顺序遍历二叉树的方法,统计树中度为1的结点数目 - CSDN
精华内容
参与话题
  • 只需要将insert里面的while循环改成下面这个样子就行了,思路是insert的时候,节点每往左移动一次,那么说明它比右边的都要小,所以加上右边的数目,而红黑的旋转并不会影响 while (next!=t->nil) { prev=...

    只需要将insert里面的while循环改成下面这个样子就行了,思路是insert的时候,节点每往左移动一次,那么说明它比右边的都要小,所以加上右边的数目,而红黑树的旋转并不会影响

    	while (next!=t->nil)
    	{
    		prev=next;
    		next=new->n<next->n?next->l:next->r;
    		count=new->n<prev->n?count+prev->size-next->size:count;/*这里千万不要用next是否是prev的左指针判断!因为左右孩子可能都是nil,这样会出错*/
    		(prev->size)++;/*插入时经过节点size+1,不需要考虑新增节点是根节点的情况*/
    	}


    展开全文
  • 顺序统计树

    千次阅读 2011-06-08 21:12:00
    在包含n个元素的无序集合中,寻找第i个顺序...这就是下面会提到的基于红黑树的顺序统计树。 相比于基础的数据结构,顺序统计树增加了一个域size[x]。这个域包含以x为根的子树的节点数(包含x本身)。size域满足等式: 

          在包含n个元素的无序集合中,寻找第i个顺序统计量的时间复杂度为O(n)。通过建立一种特定的结构,可以使得任意的顺序统计量都可以在O(lgn)的时间内找到。这就是下面会提到的基于红黑树的顺序统计树。

          相比于基础的数据结构,顺序统计树增加了一个域size[x]。这个域包含以x为根的子树的节点数(包含x本身)。size域满足等式:

                                             size[x] = size[left[x]] + size[right[x]] + 1

         再根据红黑树的排序特性,我们就可以O(lgn)的时间内完成下面的操作。

         顺序统计树如下图所示:

        

    查找第i小的元素

          实现OS-SELECT(x, i)返回以x为根的子树中包含第i小关键字的节点的指针。根据排序树的性质,我们知道左子树的键值要小于根节点的键值,右节点的键值要大于根节点,这相当于静态的顺序统计量的PARTITION已经完成。同时我们知道左右子树的大小,我们就可以确定在哪个分支进行接下来的查找。

         OS-SELECT(x, i) 整个过程如下:

     

    每次调用,必定会下降一层,故OS-SELECT的时间复杂度为O(lgn)

     

    确定一个元素的秩

          这里的秩指的是节点x在线性序中的位置。根据排序树的性质,也就是节点x在中序遍历中的位置。利用中序遍历的特性就可以得到。

          OS-RANK(T, x) 整个过程如下:

     

     每次必然至少上升一层,故OS-RANK的时间复杂度为O(lgn)

     

          建立顺序统计树的时间为O(nlgn),那和一般的静态查找O(n)相比,岂不是更加复杂?其实,这两种方法应用的场合不一样,如果只查找一次或几次,静态查找比较快速,如果多次查找(查找次数和n具有可比性),那么顺序统计树就体现出它的优点了。另外,顺序统计树还可以方便快速(O(lgn)时间内)的支持元素的插入和删除,这两点是静态顺序统计量方法无法比拟的。

     

    问题思考,如何利用顺序统计树来解决一些问题呢?

     

    14.1-5 给定n个元素的顺序统计树中的一个元素x和一个自然数i,如何在O(nlgn)时间内,确定x该树的线性序中第i个后继?

    分析与解答:

         首先利用元素x得到它的秩r,然后查找第i+r小的元素即可.

        OS-RANK(T, x, i)的整个过程如下: 

     

     

      14.1-7 说明如何在O(nlgn)的时间内,利用顺序统计树对大小为n的数组中的逆序对进行计数)

     

      分析与解答:

            如果这n个元素的数组记为a1, a2, a3, ... , ai , ... , an,那么我们可以依次求出以第i个元素ai结尾的逆序对<aj, ai>,j<i 的个数vi。

    那么总的逆序对的个数为v

                                          v = v1 + v2+ ... + vn

            可以这样考虑,动态集合a1, a2, ... , ai中我们可以求出ai的秩(也就是说ai在排序后的序列中的位置),若为其秩为r,则逆序对的数量

                                          vi = i - r

      如此我们便可以迭代的求取。

     

     

     

    14-2 Josephus排列

       Josephus问题的定义如下:假设n个人排成环形,且有一正整数m<=n。从某个指定的人开始,沿环报数,每遇到第n个人就让其出列,且报数进行下去。这个过程一直进行到所有人都出列为止。每个人出列的次序定义了整数1, 2, ..., n的(n, m)-Josephus排列。例如,(7, 3)-Josephus排列为<3, 6, 2, 7, 5, 1, 4>。

    a)假设m为常数。请描述一个O(n)时间的算法,使之给定的整数n,输出(n, m)-Josephus排列

    b)假设m不是常数。请描述一个O(nlgn)时间的算法,使之给定的整数n和m,输出(n, m)-Josephus排列

    分析与解答:

         a)每个人对应一个元素,共n个元素,键值为编号。将这n个元素构成一个循环双链表,那么每次让一个人出列的时间复杂度为O(m)总的时间复杂度为O(nm),由于m是常数,则为O(n)的时间复杂度。

         b)若m不是常数,则正好可以使用顺序统计树来动态的进行处理。每次选择出列一个元素,在顺序统计树中将其删除,并重新查找,迭代进行。如果之前删除的是当前集合的第j个位置的元素,那么下一次删除的是剩余集合的j-1+m个位置的元素,并对剩余集合的元素个数取模。整个过程如下

     

     

     

     

    展开全文
  • 改进的顺序统计树

    问题:通过为结点增加指针的方式,试说明如何在扩张的顺序统计树上,支持每一动态集合查询操作MINIMUM,MAXIMUM,SUCCESSOR和PREDECESSOR在最坏时间O(1)内完成。顺序统计树上的其他操作的渐近性能不应受影响。

    代码如下:

    //本程序在原有的红黑树基础上增加了子树结点个数,前驱后继结点以及最大小结点属性。
    #include <iostream>
    #include <time.h>
    using namespace std;
    #define BLACK 0
    #define RED 1
    #define Nil -1
    #define n  20 //更改顺序统计树内的结点数。
    #define LEN sizeof(struct OS_Tree)
    struct OS_Tree
    {
       struct OS_Tree*right,*left;
       struct OS_Tree*parent;
       struct OS_Tree*next,*prev;
       struct OS_Tree* Max,*Min;
       int key,color,size;//size表示子树的结点数。
    };
    struct OS_Tree*root=NULL,*nil=NULL,*head=NULL,*tail=NULL;
    void LEFT_ROTATE(struct OS_Tree*x)
    {//左旋转:分三个步骤①②③来叙述旋转代码的。
    	struct OS_Tree*y=x->right;//设置y结点。
    	if(y->left!=nil)x->Max=y->left->Max;//对附加信息的维护
    	else x->Max=x;
    	y->Min=x->Min;
    	x->right=y->left;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
    	if(y->left!=nil)
    	{
           y->left->parent=x;
    	}
    	y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
    	if(x->parent==nil)
    	{
           root=y;
    	}
    	else if(x==x->parent->left)
    	{
           x->parent->left=y;
    	}
    	else x->parent->right=y;
    	y->left=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
    	x->parent=y;  
        y->size = x->size;  //对附加信息的维护
        x->size = x->left->size + x->right->size +1; 
    }
    void RIGHT_ROTATE(struct OS_Tree*x)
    {//右旋转:分三个步骤①②③来叙述旋转代码的。
    	struct OS_Tree*y=x->left;//设置y结点。
    	if(y->right!=nil) x->Min=y->right->Min;//对附加信息的维护
    	else x->Min=x;
    	y->Max=x->Max;
    	x->left=y->right;//本行代码以及下面的if结构表达的是“y的左孩子成为x的右孩子”。①
    	if(y->right!=nil)
    	{
    		y->right->parent=x;
    	}
    	y->parent=x->parent;//本行代码以及下面的if-else结构表达的过程是“y成为该子树新的根”。②
    	if(x->parent==nil)
    	{
    		root=y;
    	}
    	else if(x==x->parent->right)
    	{
    		x->parent->right=y;
    	}
    	else x->parent->left=y;
    	y->right=x;//本行代码以及下面一行都表达了“x成为y的左孩子”。③
    	x->parent=y;
    	y->size = x->size;  //对附加信息的维护
        x->size = x->left->size + x->right->size +1; 
    }
    void RB_INSERT_FIXUP(struct OS_Tree*z)
    {
       while (z->parent->color==RED)
       {
    	   if (z->parent==z->parent->parent->left)
    	   {
    		   struct OS_Tree*y=z->parent->parent->right;//叔结点
    		   if (y->color==RED)//情况一:叔结点为红色
    		   {//给p1,y,p2着色以保持性质5。并且解决了z的父结点和z都是红色结点问题
    			   z->parent->color=BLACK;
    			   y->color=BLACK;
    			   z->parent->parent->color=RED;
    			   z=z->parent->parent;//把z的祖父结点当成新结点z进入下一次循环
    		   } 
    		   else 
    		   {
    			   if (z==z->parent->right)//情况二:检查z是否是一个右孩子且叔结点为黑色,前提是p1结点不是叶子结点
    			   {//使用一个左旋让情况2转变为情况3
    				   z=z->parent;
    				   LEFT_ROTATE(z);//由于进入if语句后可知旋转结点不可能是叶子结点,这样就不用判断z是否是叶子结点了。
    			   } 
                   z->parent->color=BLACK;//情况三:是z是一个左孩子且叔结点为黑色,改变z的父和祖父结点颜色并做一次右旋,以保持性质5
    			   z->parent->parent->color=RED;
    			   RIGHT_ROTATE(z->parent->parent);//由于p2可能是叶子结点,所以最好还是用一个if判断
    		   }
    	   } 
    	   else//下面else分支类似于上面,注意到else分支的情况2和情况3所做旋转正好是if分支情况的逆。
    	   {
    		   struct OS_Tree*y=z->parent->parent->left;
    		   if (y->color==RED)
    		   {
    			   z->parent->color=BLACK;
    			   y->color=BLACK;
    			   z->parent->parent->color=RED;
    			   z=z->parent->parent;
    		   } 
    		   else 
    		   {
    			   if (z==z->parent->left)
    			   {
    				   z=z->parent;
    				   RIGHT_ROTATE(z);
    			   } 
                   z->parent->color=BLACK;
    			   z->parent->parent->color=RED;
    			   LEFT_ROTATE(z->parent->parent);
    		   }
    	   }
       }
       root->color=BLACK;//最后给根结点着为黑色。
    }
    void RB_INSERT(struct OS_Tree*z)
    {
    	struct OS_Tree*y=nil;
    	struct OS_Tree*x=root;
    	while (x!=nil)
    	{
    		x->size++;
    		y=x;  
    		if (z->key<x->key)
    		{
    			x=x->left;
    		}
    		else x=x->right;
    	}
    	z->parent=y;
    	if (y==nil)
    	{
    		tail=head=root=z;
    		root->next=nil;
    		root->prev=nil;
    	} 
    	else if(z->key<y->key)
    	{
    		y->left=z;
    		z->next=y;
    		y->prev=z;
    		while (y)
    		{ 
    			y->Min=z;
    			if (y->parent==nil||y->parent->right==y)
    			{
    				break;
    			}
    		   y=y->parent;
    		}
    		if (y->parent==nil)
    		{
    			head=z;
    			z->prev=nil;
    		}
    		else if (y->parent->right==y)
    		{
    			y->parent->next=z;
    		    z->prev=y->parent;
    		}
    	}
    	else 
    	{
    		y->right=z;
    		z->prev=y;
    		y->next=z;
    		while (y)
    		{
    			y->Max=z;
    			if (y->parent==nil||y->parent->left==y)
    			{
    				break;
    			}
    			y=y->parent;
    		}
    		if (y->parent==nil)
    		{
    			tail=z;
    			z->next=nil;
    		}
    		else if (y->parent->left==y)
    		{
    			y->parent->prev=z;
    			z->next=y->parent;
    		}
    	}
    	z->left=nil;//给插入结点左右孩子赋值为空。
    	z->right=nil;
    	z->color=RED;//给插入结点着为红色。
    	z->Max=z->Min=z;
    	z->size=1;
    	z->left->size=0;
    	z->right->size=0;
    	RB_INSERT_FIXUP(z);
    	//InOderTraverse(root);
    }
    void RB_TRANSPLANT(struct OS_Tree*u,struct OS_Tree*v)
    {
    	if (u->parent==nil)
    		root=v;
    	else if(u==u->parent->left)
    		u->parent->left=v;
    	else u->parent->right=v;
    	v->parent=u->parent;
    }
    struct OS_Tree*TREE_MINIMUM(struct OS_Tree*x)//求二叉查找树当前结点最小值
    {
    	return x->Min;
    }
    struct OS_Tree*TREE_MAXINUM(struct OS_Tree*x)//求二叉查找树当前结点最大值
    {
    	return x->Max;
    }
    struct OS_Tree*TREE_PREDECESSOR(struct OS_Tree*x)//查找二叉查找树的前驱
    {
    	return x->prev;
    }
    struct OS_Tree*TREE_SUCCESSOR(struct OS_Tree*x)//查找二叉查找树的后继
    {
    	return x->next;
    }
    //非递归版本的二叉查找树查找函数
    struct OS_Tree*ITERATIVE_TREE_SEARCH(struct OS_Tree*x,int k)
    {
    	while (x!=nil&&k!=x->key)
    	{
    		if (k<x->key)
    		{
    			x=x->left;
    		}
    		else x=x->right;
    	}
    	return x;
    }
    void RB_DELETE_FIXUP(struct OS_Tree*x)
    {
    	
    	 struct OS_Tree*w=NULL;//w是x的兄弟结点
         while (x!=root&&x->color==BLACK)//如果x是黑色并且不是根结点,才进行循环。
         {//x是一个具有双重颜色的结点,调整的目的是把x的黑色属性向上移动。
    		 if (x==x->parent->left)
    		 {
    			 w=x->parent->right;
    			 if (w->color==RED)//情况一:x的兄弟结点w是红色的。
    			 {//改变w和x.p的颜色+一次旋转使其变为情况二,三,四。
    				 w->color=BLACK;
    				 x->parent->color=RED;
    				 LEFT_ROTATE(x->parent);
    				 w=x->parent->right;
    			 }
    			 if (w->left->color==BLACK&&w->right->color==BLACK)//情况二:x的兄弟结点w是黑色的,而且w的两个子节点都是黑色。
    			 {
    				 w->color=RED;//从x和w上去掉一重黑色。x还是黑色,而w变为红色。
    				 x=x->parent;//x结点向上移动成为新的待调整结点。
    			 }
    			 else
    			 {
    				 if (w->right->color==BLACK)//情况三:x的兄弟结点w是黑色的,w的左孩子是红色的,w的右孩子是黑色的。
    				 {//交换w和w.left的颜色+旋转使其转变为情况四。
    					 w->left->color=BLACK;
    					 w->color=RED;
    					 RIGHT_ROTATE(w);
    					 w=x->parent->right;
    				 }
    				 w->color=x->parent->color;//以下是情况四:x的兄弟结点w是黑色的,且w的右孩子是红色的。
    				 x->parent->color=BLACK;//置x.p和w.right为黑色+旋转使其去掉x的额外黑色。
    				 w->right->color=BLACK;
    				 LEFT_ROTATE(x->parent);
    				 x=root;//x成为根结点,结束循环。
    			 }
    		 } 
    		 else//以下和上面的if分支类似,不做累述。
    		 {
                 w=x->parent->left;
    			 if (w->color==RED)
    			 {
    				 w->color=BLACK;
    				 x->parent->color=RED;
    				 RIGHT_ROTATE(x->parent);
    				 w=x->parent->left;
    			 }
    			 if (w->left->color==BLACK&&w->right->color==BLACK)
    			 {
    				 w->color=RED;
    				 x=x->parent;
    			 }
    			 else
    			 {
    				 if (w->left->color==BLACK)
    				 {
    					 w->right->color=BLACK;
    					 w->color=RED;
    					 LEFT_ROTATE(w);
    					 w=x->parent->left;
    				 }
    				 w->color=x->parent->color;
    				 x->parent->color=BLACK;
    				 w->left->color=BLACK;
    				 RIGHT_ROTATE(x->parent);
    				 x=root;
    			 }
    		 }
         }x->color=BLACK;
    }
    void RB_DELETE(struct OS_Tree*z)
    {
        struct OS_Tree*y=z,*x;//y为待删除或待移动结点
    	int y_original_color=y->color;//保存y的原始颜色,为做最后的调整做准备。
    	struct OS_Tree*k=z->parent,*p=z->parent,*t=z->parent;
    	if (z->left==nil)
    	{
    		while (t!=nil)
    		{
    			t->size--;
    			t=t->parent;
    		}
    		x=z->right;//x指向y的唯一子结点或者是叶子结点,保存x的踪迹使其移动到y的原始位置上
    		if (z->parent->left==z)
    		{
    			if (x!=nil)
    			{
    				while (p!=nil&&p->parent->left==p)
    				{
    					p->Min=x->Min;
    					p=p->parent;
    				}
    				p->Min=x->Min;
    			} 
    			else
    			{
    				while (p!=nil&&p->parent->left==p)
    				{
    					p->Min=k;
    					p=p->parent;
    				}
    			    p->Min=k;
    			}
    		}
    		else 
    		{
    			if (x!=nil)
    			{
    				while(p!=nil&&p->parent->right==p)
    				{
                        p->Max=x->Max;
    					p=p->parent;
    				}
                    p->Max=x->Max;
    			} 
    			else
    			{
    				while (p!=nil&&p->parent->right==p)
    				{
    					p->Max=k;
    					p=p->parent;
    				}
    		        p->Max=k;
    			}
    		}
    		RB_TRANSPLANT(z,z->right);//把以z.right为根的子树替换以z为根的子树。
    	}
    	else if (z->right==nil)
    	{
    		while (t!=nil)
    		{
    			t->size--;
    			t=t->parent;
    		}
    		x=z->left;//x指向y的唯一子结点或者是叶子结点,保存x的踪迹使其移动到y的原始位置上
    		if(z->parent->right==z)
    		{
    			while (p!=nil&&p->parent->right==p)
    			{
    				p->Max=x->Max;
    				p=p->parent;
    			}
                p->Max=x->Max;
    		}
    		else 
    		{
    			while (p!=nil&&p->parent->left==p)
    			{
    				p->Min=x->Min;
    				p=p->parent;
    			}
                 p->Min=x->Min;
    		}
    		RB_TRANSPLANT(z,z->left);//把以z.left为根的子树替换以z为根的子树。
    	}
    	else 
    	{
    		y=TREE_MINIMUM(z->right);//找到z.right的后继。
    		struct OS_Tree*t=y->parent;
    		y->size=z->size-1;//y替换z原来的位置,所以size属性在待删除结点z基础上-1
    		while (t!=nil)
    		{
    			t->size--;
    			t=t->parent;
    		}
            y_original_color=y->color;//y的新的原始结点被重置。
    		x=y->right;//x指向y的唯一子结点或者是叶子结点,保存x的踪迹使其移动到y的原始位置上
    		y->Min=z->left->Min;//+
    		if (y->parent==z)
    		{
    			x->parent=y;//由于z的父结点是要删除的结点,所以不能指向它,于是指向y
    		} 
    		else
    		{
    			struct OS_Tree*w=z->right;
    			if (y->right!=nil)
    			{
    				while (w->left!=nil)
    				{
    					w->Min=x->Min;
    					w=w->left;
    				}
    			}
    			else
    			{
    				while (w->left!=nil)
    				{
    					w->Min=y->parent;
    					w=w->left;
    				}
    			}
    			y->Max=z->Max;//+
    			RB_TRANSPLANT(y,y->right);//把以y.right为根的子树替换以y为根的子树。
    			y->right=z->right;
    			y->right->parent=y;
    		}
    		RB_TRANSPLANT(z,y);//把以y为根的子树替换以z为根的子树。
    		y->left=z->left;
    		y->left->parent=y;
    		y->color=z->color;//把已经删除的结点颜色赋值给y,保证了y以上的树结构红黑性质不变。
    	}
    	if (z->prev==nil)
    	{
            head=z->next;
    	}
    	if (z->next==nil)
    	{
    		tail=z->prev;
    	}
    	z->prev->next=z->next;
    	z->next->prev=z->prev;
    	if(y_original_color==BLACK) //y的原始颜色为黑色,说明需要调整红黑颜色。
    		RB_DELETE_FIXUP(x);
    }
    //中序遍历
    void InOderTraverse(struct OS_Tree *p)
    {
        if (p!=nil)
    	{		
    		InOderTraverse(p->left);
    		cout<<p->key<<" "<<p->color<<" "<<"最大值:"<<p->Max->key<<"最小值:"<<p->Min->key<<"秩:"<<p->size<<endl;
    		InOderTraverse(p->right);
    	}
    }
    int RAND(int a[],int i)//随机选择N个互不相同的数。
    {
    	int k=rand()%n+1;
    	for (int j=0;j<i;j++)
    	{
    		if (a[j]==k)
    		{
    			k=rand()%n+1;
    			j=-1;
    		}
    	}
    	return k;
    }
    struct OS_Tree*OS_SELECT(struct OS_Tree*x,int i)//查找顺序统计树给定秩的元素
    {
       int r=x->left->size+1;
       if (i==r)
       {
    	   return x;
       }
       else if (i<r)
       {
    	   return OS_SELECT(x->left,i);
       }
       else return OS_SELECT(x->right,i-r);
    }
    int OS_RANK(struct OS_Tree*T,struct OS_Tree*x)//确定顺序统计树的秩
    {
       int r=x->left->size+1;
       struct OS_Tree*y=x;
       while (y!=root)
       {
    	   if (y==y->parent->right)
    	   {
    		   r=r+y->parent->left->size+1;
    	   }
    	   y=y->parent;
       }
       return r;
    }
    void main()
    {
    	//srand( (unsigned)time( NULL ) );
    	int array1[n]={0};
    	for (int j=0;j<n;j++)
    	{
    		array1[j]=RAND(array1,j);
    		cout<<array1[j]<<" ";
    	}
    	cout<<endl;
    	nil=new struct OS_Tree[LEN];
    	nil->key=Nil;nil->color=BLACK;
    	root=nil;
    	int i=0;
    	struct OS_Tree*ROOT=new struct OS_Tree[LEN];
    	ROOT->key=array1[i++];
    	RB_INSERT(ROOT);
    	root=ROOT;
        while (i!=n)
        {
    		struct OS_Tree*z=new struct OS_Tree[LEN];
    		z->key=array1[i];
    		RB_INSERT(z);
    		i++;
        }
    	InOderTraverse(root);
    	cout<<endl;
    	struct OS_Tree*x=NULL;
    	i=0;
    	while(i!=n)
    	{
    		x=ITERATIVE_TREE_SEARCH(root,array1[i]);
    		cout<<OS_RANK(root,x)<<endl;
    		RB_DELETE(x);
    		cout<<"删除"<<array1[i++]<<"后中序遍历:"<<endl;
    		InOderTraverse(root);
    	}
    	cout<<endl;
    }
    总结:以上程序适当地对插入和删除函数进行修改,修改部分只是增加了O(lgn)时间的常系数,比如在插入过程中,需要从叶结点向上遍历到根结点,遍历这段路径只需O(lgn)时间,删除函数也有类似情况。其他函数有的增加了常数时间,有的未作改动。总体来看,在增加新属性的基础上,除求最值和前驱后继操作时间变为O(1),其他操作渐进性能均不受影响。

    
    展开全文
  • #include using namespace std; class BRTree; class BRTreeNode{ private: friend class BRTree; int key; bool color; int size; BRTreeNode *left; BRTreeNode *right; BRTreeNode *parent;... //创
    #include<iostream>
    using namespace std;
    class BRTree;
    class BRTreeNode{
    private:
    	friend class BRTree;
    	int key;
    	bool  color;
    	int size;
    	BRTreeNode *left;
    	BRTreeNode *right;
    	BRTreeNode *parent;
    public:
    	//创建一个默认构造函数
    	BRTreeNode():key(-1),color(0),size(0),left(NULL),right(NULL),parent(NULL){}
    	//创建一个拷贝构造函数
    	BRTreeNode(BRTreeNode *node):key(node->key),color(node->color),size(node->size),left(node->left),right(node->right),parent(node->parent){}
    	//创建一个含有参数的构造函数
    	BRTreeNode(int num,int flag,int value):key(num),color(flag),size(value),left(NULL),right(NULL),parent(NULL){}
    	//下面创建一个析构函数
    	~BRTreeNode()
    	{}
    	//下面定义一个返回结点值的函数
    	int getkey()
    	{
    		return key;
    	}
    	//下面定义一个返回标记的函数
    	bool getcolor()
    	{
    		return this->color;
    	}
    	 BRTreeNode* GetLeft()  
        {  
            return this->left;  
        }  
        BRTreeNode* Getright()  
        {  
            return this->right;  
        }  
        BRTreeNode* Getparent()  
        {  
            return this->parent;  
        } 
    	void inorder()
    	{
    		if(this!=NULL)
    		{
    			this->left->inorder();
    			cout<<"中序遍历的值是"<<this->key<<endl;
    			this->right->inorder();
    		}
    	}
    	//下面定义一个前序遍历的函数
    	void preorder()
    	{
    		if(this!=NULL)
    		{
    			cout<<"前序遍历的结果是"<<this->key<<endl;
    			this->left->preorder();
    			this->right->preorder();
    		}
    	}
    	//6
    	  void Postorder()  
        {  
            if(this!=NULL)  
            {  
                this->left->Postorder();  
                this->right->Postorder();  
                cout<<this->key<<" ";  
            }  
        }
        void make_empty()
    	{
    		if(this!=NULL)
    		{
    			this->left->make_empty();
    			this->right->make_empty();
    			delete this;
    		}
    	}
    	int getheight()
    	{
    		int L,R;
    		if(this==NULL)
    		{
    			return 0;
    		}
    		L=this->left->getheight();
    		R=this->right->getheight();
    		return 1+(L>R)?L:R;
    	}
    
    
    };
    
    
    class BRTree{
    private:
    	BRTreeNode *root;
    	BRTreeNode *nil;
    public:
    	BRTree():nil(new BRTreeNode())
    	{
    		nil->color=0;
    		nil->key=-1;
    		nil->left=nil->right=nil->parent=NULL;
    		root=nil;
    	}
    	//下面定义一个以清空node为根结点的树
    	 void MakeEmpty(BRTreeNode*node)  
        {  
            if(node!=nil)  
            {  
                MakeEmpty(node->left);  
                MakeEmpty(node->right);  
                delete node;  
            }  
        }  
        int Getkey(BRTreeNode* node)  
        {  
    		return node->getkey();  
        }  
        bool Getcolor(BRTreeNode* node)  
        {  
    		return node->getcolor();  
        }  
        BRTreeNode* Getroot()  
        {  
            return root;  
        }  
        BRTreeNode* GetParent(BRTreeNode*node)  
        {  
            return node->parent;  
        }  
        int GetHeight(BRTreeNode *node)  
        {  
            int L,R;  
            if(node==nil)  
                return 0;  
            L=GetHeight(node->left);  
            R=GetHeight(node->right);  
            return 1+(L>R? L:R);  
        }  
        void Inorder(BRTreeNode *node)  
        {  
            if(node!=nil)  
            {  
                Inorder(node->left);  
                cout<<node->key<<" ";  
                Inorder(node->right);  
            }  
        }  
        void Preorder(BRTreeNode *node)  
        {  
            if(node!=nil)  
            {  
                cout<<node->key<<" ";  
                Preorder(node->left);  
                Preorder(node->right);  
            }  
        }  
        void Posetorder(BRTreeNode*node)  
        {  
            if(node!=nil)  
            {  
                Posetorder(node->left);  
                Posetorder(node->right);  
                cout<<node->key<<" ";  
            }  
        }   
        //左旋节点node  
        bool LeftRotate(BRTreeNode* node)  
        {  
            BRTreeNode *y;  
            if(node->right==nil)  
            {  
                cout<<"can't left rotate!"<<endl;  
                return 0;  
            }  
            y=node->right;  
            node->right=y->left;  
            if(y->left!=nil)  
            {  
                y->left->parent=node;  
            }  
            y->parent=node->parent;  
            if(node->parent==nil)  
            {  
                root=y;  
            }  
            else if(node->parent->left==node)  
            {  
                node->parent->left=y;  
            }  
            else  
            {  
                node->parent->right=y;  
            }  
            y->left=node;  
            node->parent=y;
    		//调整size域的大小
    		y->size=node->size;
    		node->size=node->left->size+node->right->size;
            return 1;  
        }  
    
    
    
    
    	  //下面定义的是一个右旋函数
         bool RightRotate(BRTreeNode* node)  
          {  
            if(node->left==nil)  
            {  
                cout<<"can't rightrotate!"<<endl;  
                return 0;  
            }  
            BRTreeNode* x;  
            x=node->left;  
            node->left=x->right;  
            if(x->right!=nil)  
            {  
                x->right->parent=node;  
            }  
            x->parent=node->parent;  
            if(node->parent==nil)  
            {  
                root=x;  
            }  
            else if(node->parent->left==node)  
            {  
                node->parent->left=x;  
            }  
            else  
            {  
                node->parent->right=x;  
            }  
            node->parent=x;  
            x->right=node;  
    		x->size=node->size;
    		node->size=node->left->size+node->right->size;
            return 1;  
          }  
    
    	//插入一个值
    	 void Insert(int num)  
        {  
            BRTreeNode* node=new BRTreeNode(num,1,1);  
            node->left=nil;  
            node->right=nil;  
            node->parent=nil;  
            BRTreeNode* p=root,*q=nil;  
            if(root==nil)  
            {  
                node->color=0;  
                root=node;  
                root->left=root->right=root->parent=nil;  
    			root->size=1;
                return ;  
            }  
            while(p!=nil)  
            {  
                if(p->key==num)  
                {  
                    cout<<num<<"  has exist!"<<endl;  
                    return ;  
                } 
    			
                else if(p->key>num)  
    			{   p->size+=1;
    				q=p;  
                    p=p->left;  
                }  
                else  
                {  p->size+=1;
                    q=p;  
                    p=p->right;  
                }  
            } 
    
            if(q->key>num)  
            {  
                q->left=node;  
                node->parent=q;  
            }  
            else  
            {  
                q->right=node;  
                node->parent=q;  
            }  
            RBInsertAdjust(node);  
        }  
    	 void RBInsertAdjust(BRTreeNode* node)  
        {  
            BRTreeNode* y;  
            while(node->parent->color==1)  
            {  
                if(node->parent==node->parent->parent->left)  
                {  
                    y=node->parent->parent->right;  
                    if(y->color==1)  
                    {  
                        node->parent->color=0;  
                        y->color=0;  
                        y->parent->color=1;  
                        node=node->parent->parent;  
                    }  
                    //此时y的颜色是黑色  
                    else   
                    {  
                        //第二种情况  
                        if(node==node->parent->right)  
                        {  
                            node=node->parent;  
                            LeftRotate(node);  
                        }  
                        //第三种情况  
                        node->parent->color=0;  
                        node->parent->parent->color=1;  
                        RightRotate(node->parent->parent);  
                    }     
                }  
                else  
                {  
                    y=node->parent->parent->left;  
                    if(y->color==1)  
                    {  
                        node->parent->color=0;  
                        y->color=0;  
                        y->parent->color=1;  
                        node=node->parent->parent;  
                    }  
                    else   
                    {  
                        if(node==node->parent->left)  
                        {  
                            node=node->parent;  
                            RightRotate(node);  
                        }  
                        node->parent->color=0;  
                        node->parent->parent->color=1;  
                        LeftRotate(node->parent->parent);  
                    }  
                }  
            }  
            root->color=0;  
        } 
    	 //搜索某个值
    	  BRTreeNode* Search(int num)  
        {  
            BRTreeNode* p=root;  
            while(p!=nil)  
            {  
                if(p->key==num)  
                {  
                    return p;  
                }  
                else if(p->key>num)  
                {  
                    p=p->left;  
                }  
                else   
                {  
                    p=p->right;  
                }  
            }  
            cout<<"there is no "<<num<<" in this tree!"<<endl;  
            return nil;  
        }  
        //获取以node节点为根节点的树的最小元素,并返回该最小值 
    	  int Minnum(BRTreeNode*node)  
        {  
            BRTreeNode*p=node;  
            while(p->left!=nil)  
            {  
                p=p->left;  
            }  
            return p->key;  
        }  
        //获取以node节点为根节点的树的最da元素,并返回该最da值  
        int Maxnum(BRTreeNode*node)  
        {  
            BRTreeNode*p=node;  
            while(p->right!=nil)  
            {  
                p=p->right;  
            }  
            return p->key;  
        }  
        //获取以node节点为根节点的树的最小元素,并返回该节点  
        BRTreeNode* MinNum(BRTreeNode*node)  
        {  
            BRTreeNode*p=node;  
            while(p->left!=nil)  
            {  
                p=p->left;  
            }  
            return p;  
        }  
        //获取以node节点为根节点的树的最大元素  
        BRTreeNode* MaxNum(BRTreeNode*node)  
        {  
            BRTreeNode*p=node;  
            while(p->right!=nil)  
            {  
                p=p->right;  
            }  
            return p;  
        }  
    
    
    
    
    
    	 BRTreeNode*InorderSuccessor(BRTreeNode*node)  
        {  
            if(node->right!=nil)  
            {  
                return MinNum(node->right);  
            }  
            else  
            {  
                BRTreeNode*p=GetParent(node);  
                while(p&&node==p->right)  
                {  
                    node=p;  
                    p=GetParent(node);  
                }  
                return p;  
            }  
        }  
        //中序遍历的前趋  
        BRTreeNode*InordePredecessor(BRTreeNode*node)  
        {  
            if(node->left!=nil)  
            {  
                return MaxNum(node->left);  
            }  
            else  
            {  
                BRTreeNode*p=GetParent(node);  
                while(p&&node==p->left)  
                {  
                    node=p;  
                    p=GetParent(node);  
                }  
                return p;  
            }     
        }  
        bool Delete(int num)  
        {  
            BRTreeNode*z,*y,*x;    
            //寻找key值为num的节点p    
            z=Search(num);   
            //如果没有该节点则返回0  
            if(z==nil)    
            {    
                return 0;    
            }  
            if(z->left==nil||z->right==nil)  
            {  
                y=z;  
            }  
            else  
                y=InorderSuccessor(z);  
            if(y->left!=nil)  
                x=y->left;  
            else  
                x=y->right;  
            x->parent=y->parent;  
            if(x->parent==nil)  
                root=x;  
            else if(y=y->parent->left)  
                y->parent->left=x;  
            else  
                y->parent->right=x;  
    		while(y!=root)
    		{
    			y->parent->size=y->parent->size-1;
    			y=y->parent;
    		}
            if(y!=z)  
            {  
                z->key=y->key;  
            }  
            if(y->color==0)  
            {  
                RBTreeFixup(x);  
            }  
            return 1;  
        }  
        void RBTreeFixup(BRTreeNode* x)  
        {  
            BRTreeNode *w;  
            while(x!=root&&x->color==0)  
            {  
                if(x==x->parent->left)  
                {  
                    w=x->parent->right;  
                    if(w->color==1)  
                    {  
                        w->color=0;  
                        x->parent->color=1;  
                        LeftRotate(x->parent);  
                        w=x->parent->right;  
                    }  
                    if(w->left->color==0&&w->right->color==0)  
                    {  
                        w->color=1;  
                        x=x->parent;  
                    }  
                    else   
                    {  
                        if(w->right->color==0)  
                        {  
                            w->color=1;  
                            RightRotate(w);  
                            w=x->parent->right;  
                        }  
                        w->color=x->parent->color;  
                        x->parent->color=0;  
                        w->right->color=0;  
                        LeftRotate(x->parent);  
                        x=root;  
                    }  
                }  
                else  
                {  
                    w=x->parent->left;  
                    if(w->color==1)  
                    {  
                        w->color=0;  
                        x->parent->color=1;  
                        RightRotate(x->parent);  
                        w=x->parent->left;  
                    }  
                    if(w->right->color==0&&w->left->color==0)  
                    {  
                        w->color=1;  
                        x=x->parent;  
                    }  
                    else   
                    {  
                        if(w->left->color==0)  
                        {  
                            w->color=1;  
                            LeftRotate(w);  
                            w=x->parent->left;  
                        }  
                        w->color=x->parent->color;  
                        x->parent->color=0;  
                        w->left->color=0;  
                        RightRotate(x->parent);  
                        x=root;  
                    }  
                }  
            }  
            x->color=0;  
        }  
    	//下面根据统计秩来找出相应的元素,其实也就是中序排列所处的位置
    
    	~BRTree()
    	{
    		MakeEmpty(root); 
    		delete nil;
    	}
    
    	BRTreeNode *os_select(BRTreeNode *startnode,int i)
    	{
    		int r=startnode->size+1;
    		if(r==i)
    		{
    			return startnode;
    		}
    		else if(i<r)
    		{
    			return os_select(startnode->left,i);
    		}
    		else
    		{
    			return os_select(startnode->right,i-r);
    		}
    	}
    	//下面定义一个给定结点的指针来找出其秩的函数
    	int os_rank(BRTreeNode *startnode)
    	{
    		int r=startnode->left->size+1;
    		BRTreeNode *y=startnode;
    		while(y!=root)
    		{
    			if(y==y->parent->right)
    			{
    				r+=y->parent->left->size+1;
    			}
    			y=y->parent;
    		}
    		return r;
    	}
    
    };
    int main()
    {   
    	
    	BRTree tree;  
        int a[8]={11,2,1,7,5,8,14,15};  
        int i;  
        for(i=0;i<8;i++)  
        {  
            tree.Insert(a[i]);  
        }  
        tree.Inorder(tree.Getroot());  //输出的结果是从小到大输出,其结果是1 2 5 7 8 11 14 15;
        cout<<endl;  
        /*tree.Insert(4);  //插入一个的值是为4的;
        tree.Inorder(tree.Getroot());  //中序输出插入4之后序列的结果为 1 2 4 5 7 8 11 14 15
        cout<<endl;  
        tree.Insert(6);  
        tree.Inorder(tree.Getroot());  
        cout<<endl;  
        tree.Insert(3);  
        tree.Inorder(tree.Getroot());  
        cout<<endl;  
        cout<<tree.GetHeight(tree.Getroot());  
        cout<<endl;  
        tree.Delete(2);  
        tree.Inorder(tree.Getroot());  
        cout<<endl;  */
    	tree.Insert(4);
    	 tree.Inorder(tree.Getroot());  
    	cout<<tree.os_rank(tree.Search(5))<<endl;
    
    	system("pause");
    	return 0;
    }

    展开全文
  • 一个元素的秩即为顺序统计中按照中序遍历节点x出现的线性顺序。 循环方式确定元素的秩代码如下: int RankoftheNode(BRTreeNode* x) { int r=x->left->size+1; BRTreeNode*p=x; while(p!=root) { ...
  • 利用红黑可以早lg(n)内查找任意个顺序统计量,这比前面讲到的在O(n)内查找效率要高,但是实现起来比较麻烦。在前面红黑的基础上实现就比较简单,在的节点域上加上size整型变量,用来标记以该节点为根的...
  • 在一个有序数组中,我们查找出现频率最高的元素,很简单,顺序扫描一遍即可统计出。那么我们对二叉查找也可以用类似方式统计,因为中序遍历序列就是有序序列,所以我们在中序遍历的过程中就可以统计出出现频率最高...
  • 1. HashMap中k的值没有顺序,常用来做统计。 2.LinkedHashMap吧。它内部有一个链表,保持Key插入的顺序。迭代的时候,也是按照插入顺序迭代,而且迭代比HashMap快。 3. TreeMap的顺序是Key的自然顺序(如整数从小...
  • 数据结构中的

    万次阅读 2012-03-06 15:06:04
    数据结构中为了存储和查找的方便,用各种结构来存储文件,本章就浅谈一下各种的表示方法、特点及各自的用途,本章设计的结构包括:二叉查找(二叉排序)、平衡二叉树(AVL)、红黑、B-、B+、字典...
  • using Microsoft.AspNetCore.Builder; using Microsoft.Extensions.DependencyInjection; using Microsoft.Extensions.Hosting; using Microsoft.OpenApi.Models; using Volo.Abp; using Volo.Abp.AspNetCore.Mvc;...
  • 一步一步写算法(之排序二叉树)

    万次阅读 多人点赞 2011-10-11 00:17:44
    【 声明:版权所有,欢迎转载,请勿用于商业用途。...  前面我们讲过双向链表的数据结构。每一个循环节点有两个指针,一个指向前面一个节点,一个指向后继节点,这样所有的节点像一颗颗珍珠一样被一根线穿在了一起...
  • C++ set用法总结(整理)

    万次阅读 多人点赞 2020-09-23 10:06:17
    顺序容器包括vector、deque、list、forward_list、array、string,所有顺序容器都提供了快速顺序访问元素的能力。 关联容器包括set、map 关联容器和顺序容器有着根本的不同:关联容器中的元素是按关键字来保存和...
  • 数据结构基础概念篇

    万次阅读 多人点赞 2017-11-14 13:44:24
    数据结构一些概念 数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系,并对这种结构定义相应的运算,而且确保经过这些运算后所得到的新结构仍然是原来的结构类型。数据:所有能被输入到计算机中,且能...
  • Trie:应用于统计和排序

    万次阅读 多人点赞 2013-02-20 16:16:16
     Trie,又称单词查找、字典,是一种形结构,是一种哈希的变种,是一种用于快速检索的多叉结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。...
  • 这是一道笔试题来的,主要是用字典来解决: /****************************************** * * 描述:这是一道笔试题,要求按单词出现的次序打印出单词及其出现的次数; * * 思路:既然是笔试题,肯定要考虑...
  • 目录 基础 c/c++ 代码优化及常见错误 ...除和图外的数据结构可以使用STL: C++ STL的使用 数据结构 线性表 顺序表 循环左移(2010联考真题) 单链表 单链表相邻结点逆置(2019北邮考研真...
  • 常用数据结构介绍

    万次阅读 2017-08-08 16:06:08
    0.数组:顺序存储,随机访问  链表:链表存储,顺序访问 1.栈 2.队列 3.串 4. 1)二叉树 2)遍历二叉树: 前序(先中间,再左边,后右边) 中序(先左边,再中间,后右边) 后序(先左边,再右边,后中间) 3...
  • Fiddler使用教程

    万次阅读 多人点赞 2018-11-01 16:46:14
    #:HTTP Request的顺序,从1开始,按照页面加载请求的顺序递增 URL:请求的服务器路径和文件名,也包括GET参数 Result:HTTP响应的状态码 Protocol:请求使用的协议(如http/https/ftp) Host:请求地址的域名 Body:...
  • 没有学习过红黑的同学请参考:> Chapter 13 Red-Black Trees Chapter 14 Augmenting Data Structures教你透彻了解红黑 1.stl中的set底层用的什么数据结构?2.红黑的数据结构怎么定义的?3.红黑有哪些性质?...
1 2 3 4 5 ... 20
收藏数 77,754
精华内容 31,101
关键字:

顺序统计树