我如何开始在这个树中搜索？ [英] How do I begin searching in this TREE ?

问题描述

我正在编写一个函数来搜索是否在红黑树中找到了一个键。函数STsearchBatch应该这样做。参数是int num（我们要搜索的键的总数，Key * in（要搜索的键数组）和Item * out（如果找到或不存储结果，我们存储结果。我们将NULLitem存储到其中）显示未找到）给定的是创建红黑树的部分代码。



我的问题是我在哪里开始搜索？我如何访问它正在创建的树？我们还必须使用二进制搜索和指针算法。很抱歉我要求大量的功课帮助，但是我不能开始这个任务来提出更合适的问题。

I am writing a function to search whether a key is found in the Red-Black Tree. The function STsearchBatch is supposed to do this. the arguments are int num(the total number of keys that we want to search, Key *in (array of Keys that are to be searched) and Item *out( where we store result if found or not. We store NULLitem in it to show not found) The given is a partial code which creates the red-black tree.

My question is that where do I begin to search ? How do I access this tree that is being created ? Also we have to use binary search and pointer arithmetic. I am sorry that I am asking a big homework help but I cannot begin this assignment to ask smaller suitable questions.

// Top-down red-black tree implementation without deletions,
// so free() does not appear.

#include <stdlib.h>
#include <stdio.h>
#include "topdownRB.h"

link z,head;               // Pointers to sentinel and root
Item NULLitem=(-9999999);  // Data for sentinel

int trace=0;  // Controls trace output for insert
void STsearchBatch(int num,Key *in,Item *out)
{
};
void STselectBatch(int num,int *in,Item *out){};
void STinvSelectBatch(int num,Key *in,int *out){};

link NEW(Item item, link l, link r, int N)
// Allocates and fills in a node
{
	link x = malloc(sizeof *x);
	x->item = item;
	x->l = l;
	x->r = r;
	x->red = 1;
	x->N = N;
	return x;
}

void STinit()
{
	// Root/sentinel (head/z) starts out red, but first insert makes root black
	// and second insert makes sentinel black.
	head = (z = NEW(NULLitem, 0, 0, 0));
}

Item searchR(link h, Key v)
// Recursive search for a key
{
	Key t = key(h->item);
	if (h == z)
		return NULLitem;
	if (eq(v, t))
		return h->item;
	if (less(v, t))
		return searchR(h->l, v);
	return searchR(h->r, v);
}

Item STsearch(Key v)
{
	return searchR(head, v);
}

Item selectR(link h, int k)
// See Sedgewick - implements "zero-based indexing".
// Returns the kth smallest key where k=0 returns the smallest
// key.  Thus, this is like flattening the tree inorder into an array
// and applying k as a subscript.
{
	int t = h->l->N;

	if (h == z)
	{
		//return NULLitem;
		printf("Impossible situation in selectR\n");
		STprintTree();
		exit(0);
	}
	if (t > k)
		return selectR(h->l, k);
	if (t < k)
		return selectR(h->r, k-t-1);
	return h->item;
}

Item STselect(int k)
{
	if (k<0 || k>=head->N)
	{
		printf("Range error in STselect() k %d N %d\n",k,head->N);
		exit(0);
	}
	return selectR(head, k);
}

int invSelectR(link h, Key v)
// Inverse of selectR
{
	Key t = key(h->item);
	int work;

	if (h==z)
		return -1;  // v doesn't appear as a key
	if (eq(v, t))
		return h->l->N;
	if (less(v, t))
		return invSelectR(h->l,v);
	work=invSelectR(h->r,v);
	if (work==(-1))
		return -1;  // v doesn't appear as a key
	return 1 + h->l->N + work;
}

int STinvSelect(Key v)
{
	return invSelectR(head,v);
}

void fixN(link h)
// Fixes subtree size of h, assuming that subtrees have correct sizes
{
	h->N=h->l->N + h->r->N + 1;
}

link rotR(link h)
// Rotate right at h, i.e. flip edge between h & h->l
{
	link x = h->l;
	h->l = x->r;
	x->r = h;

	x->N = x->r->N;
	fixN(x->r);
	return x;
}

link rotL(link h)
// Rotate left at h, i.e. flip edge between h & h->r
{
	link x = h->r;
	h->r = x->l;
	x->l = h;

	x->N = x->l->N;
	fixN(x->l);
	return x;
}

link rsRBinsert(link h, Item item, int sw)
// Sedgewick's code, with details included - NOT TESTED
{
	Key v = key(item);

	if (h == z)
		return NEW(item, z, z, 1);

	if ((h->l->red) && (h->r->red))
	{
		h->red = 1;
		h->l->red = 0;
		h->r->red = 0;
	}

	if (less(v, key(h->item)))
	{
		h->l = rsRBinsert(h->l, item, 0);
		if (h->red && h->l->red && sw)
			h = rotR(h);
		if (h->l->red && h->l->l->red)
		{
			h = rotR(h);
			h->red = 0;
			h->r->red = 1;
		}
	}
	else
	{
		h->r = rsRBinsert(h->r, item, 1);
		if (h->red && h->r->red && !sw)
			h = rotL(h);
		if (h->r->red && h->r->r->red)
		{
			h = rotL(h);
			h->red = 0;
			h->l->red = 1;
		}
	}
	fixN(h);
	return h;
}

void extendedTraceOn()
{
	trace=2;
}

void basicTraceOn()
{
	trace=1;
}

void traceOff()
{
	trace=0;
}

void tracePrint(char *s,link h)
{
	if (trace) {
		if (h==z)
			printf("%s at sentinel\n",s);
		else
			printf("%s at %d\n",s,key(h->item));
	}
}

link RBinsert(link h, Item item, int sw)
// Program 13.6 coded to be a bit clearer and make mutually exclusive
// cases obvious.  Also includes tracing.  See 2320 notes.  BPW
// h is present node in search down tree.
// Returns root of modified subtree.
// item is the Item to be inserted.
// sw == 1 <=> h is to the right of its parent.
{
	Key v = key(item);
	link before;  // Used to trigger printing of an intermediate tree

	tracePrint("Down",h);
	if (h == z)
		return NEW(item, z, z, 1);  // Attach red leaf

	if ((h->l->red) && (h->r->red))      // Flip colors before searching down
	{
		tracePrint("Color flip",h);
		h->red = 1;
		h->l->red = 0;
		h->r->red = 0;
		if (trace==2)
			STprintTree();
	}

	if (less(v, key(h->item)))
	{
		tracePrint("Insert left",h);
		before=h->l;
		h->l = RBinsert(h->l, item, 0);    // Insert in left subtree
		if (trace==2 && before!=h->l)      // Has a rotation occurred?
			STprintTree();
		if (h->l->red) {
			if (h->red)
				if (sw) {
					tracePrint("Case ~1",h);
					h = rotR(h);                 // Set up case ~2 after return
				}
				else
				;
			else if (h->l->l->red) {
				tracePrint("Case 2",h);
				h = rotR(h);
				h->red = 0;
				h->r->red = 1;
			}
		}
	}
	else
	{
		tracePrint("Insert right",h);
		before=h->r;
		h->r = RBinsert(h->r, item, 1);    // Insert in right subtree
		if (trace==2 && before!=h->r)      // Has a rotation occurred?
			STprintTree();
		if (h->r->red) {
			if (h->red)
				if (!sw) {
					tracePrint("Case 1",h);
					h = rotL(h);                 // Set up case 2 after return
				}
				else
				;
			else if (h->r->r->red) {
				tracePrint("Case ~2",h);
				h = rotL(h);
				h->red = 0;
				h->l->red = 1;
			}
		}
	}

	fixN(h);
	tracePrint("Up",h);
	return h;
}

void STinsert(Item item)
{
	head = RBinsert(head, item, 0);
	// head = RBinsert(head, item, 1); // change early behavior 11/11/14
	if (head->red)
		printf("red to black reset has occurred at root!!!\n");
	head->red = 0;
}

void checkRed(link h,int redParent)
// Verifies property 3 in notes
{
	if (redParent && h->red)
	{
		printf("Red property problem at %d\n",key(h->item));
		STprintTree();
		exit(0);
	}
	if (h==z)
		return;
	checkRed(h->l,h->red);
	checkRed(h->r,h->red);
}

int leftPathBlackHeight(link h)
// Counts black nodes on path to the minimum
{
	if (h==z)
		return !(h->red);
	return leftPathBlackHeight(h->l) + !(h->red);
}

void checkBlack(link h,int blackCount)
// Checks that all paths downward from a node have the same
// number of black nodes
{
	if (h==z) {
		if (blackCount==!(h->red))
			return;
		else {
			printf("Black height problem!\n");
			STprintTree();
			exit(0);
		}
	}
	if (h->red)
	{
		checkBlack(h->l,blackCount);
		checkBlack(h->r,blackCount);
	}
	else
	{
		checkBlack(h->l,blackCount-1);
		checkBlack(h->r,blackCount-1);
	}
}

Key lastInorder;    // Saves key from last node processed

void checkInorder(link h)
// Checks that inorder yields keys in ascending order
{
	if (h==z)
		return;

	checkInorder(h->l);
	if (less(h->item,lastInorder))
	{
		printf("Inorder error\n");
		STprintTree();
		exit(0);
	}
	lastInorder=key(h->item);
	checkInorder(h->r);
}

int checkN(link h)
// Verifies that subtree sizes are correct
{
	int work;

	if (h==z)
	{
		if (h->N!=0)
		{
			printf("Count for sentinel is %d, should be 0\n",h->N);
			STprintTree();
			exit(0);
		}
	}
	else
	{
		work=checkN(h->l) + checkN(h->r) + 1;
		if (h->N!=work)
		{
			printf("Count for key %d is %d, should be %d\n",key(h->item),h->N,work);
			STprintTree();
			exit(0);
		}
	}
	return h->N;
}

void verifyRBproperties()
// Checks all required properties.
// If a fatal problem is found, the tree is printed before exit(0)
{
	int lpbHeight;

	if (head->red)
		printf("Root is not black!\n");
	if (z->red)
		printf("Sentinel is not black!\n");
	lastInorder=(-99999999);
	checkInorder(head);
	checkRed(head,0);
	lpbHeight=leftPathBlackHeight(head);
	checkBlack(head,lpbHeight);
	checkN(head);
}

void printTree(link h,int depth,int bhAbove)
{
	int i,bhBelow;

	if (h==z)
	{
		if (bhAbove!=1)
		{
			for (i=0;i<depth;i++)
			printf("     ");
			printf("Black-height issue detected at sentinel\n");
		}

		return;
	}

	if ((h->red))
		bhBelow=bhAbove;
	else
		bhBelow=bhAbove-1;
	printTree(h->r,depth+1,bhBelow);
	for (i=0;i<depth;i++)
		printf("     ");
	if (h->red)
		printf("[%d %d %d]\n",key(h->item),h->N,bhBelow);
	else
		printf("(%d %d %d)\n",key(h->item),h->N,bhBelow);
	printTree(h->l,depth+1,bhBelow);
}

void STprintTree()
{
	printTree(head,0,leftPathBlackHeight(head));
}

void fixAllN(link h)
// Recomputes subtree sizes for an otherwise correct tree
{
	if (h->l)
		fixAllN(h->l);
	else
		h->l=z;
	if (h->r)
		fixAllN(h->r);
	else
		h->r=z;
	fixN(h);
}

void cleanUpUnbalanced(link h)
// Checks a tree constructed elsewhere
{
	fixAllN(h);
	head=h;
	z->red=0;
	verifyRBproperties();
}

我的尝试：



我理解在搜索方面应该做些什么。

What I have tried:

I understand what I am supposed to do in terms of searching.

推荐答案

树的根显然是变量头。这就是所有搜索将开始的地方。例如，您可以像这样使用searchR：

The root of your tree is obviously in variable head. So that's where all searches will start. For example you could use searchR like this:

if (searchR (head, in[n]) != NULLitem)
{
  // we have found key in[0] in the tree
  ...
}

I不会给你更多，因为这是家庭作业。



BTW：你了解红黑树的原理吗？如果不是，你应该先研究它们。如果没有清楚地了解它们是如何工作的，那么剩下的工作就是浪费时间。

I will not give you more, because this is homework.

BTW: Have you understood the principals of red-black trees? If not you should study them first. Without a clear understanding of how they work the rest of this exercise is just wasted time.

这篇关于我如何开始在这个树中搜索？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！