RotSchwarzBaum

Hallo Leute ich bin zurzeit dabei einen Rotschwarz baum zu schreiben nur ständig treten irgendwelche ausnahmefehler bei meinen if's auf wollte fragen ob mir jemand helfen kann da ich hier am verzweifeln bin..

struct node *uncle(struct node *n)
{
if (n->parent != NULL)
{
if (n->parent->parent != NULL)
{
if (n->parent == n->parent->parent->right)
return n->parent->parent->left;
else
return n->parent->parent->right;
}
}
}

diese funktion wird bei jedem durchlauf aufgerufen jedoch bricht das programm ab der 2ten if ab dann steht da "Ausnahmefehler bei 0x00BB1B9D in Baumso.exe: 0xC0000005: Zugriffsverletzung beim Lesen an Position 0xCDCDCDD5" dieser fehler tritt des öfteren auf und ich hab keine ahnung wie ich es anders machen soll bitte um hilfe

Finnegan

Relo4d schrieb:

Hallo Leute ich bin zurzeit dabei einen Rotschwarz baum zu schreiben nur ständig treten irgendwelche ausnahmefehler bei meinen if's auf wollte fragen ob mir jemand helfen kann da ich hier am verzweifeln bin..
struct node *uncle(struct node *n)
{
	if (n->parent != NULL)
	{
		if (n->parent->parent != NULL)
		{
			if (n->parent == n->parent->parent->right)
				return n->parent->parent->left;
			else
				return n->parent->parent->right;
		}
	}
}
[...] [...]

1. Unter den ganzen Smileys gibts auch noch Buttons ohne Bilder: z.B. [Code] und [C++]. Damit kann man Code-Tags einfügen, die meist dazu führen dass die Leute hier etwas motivierter sind sich mit deinem Problem auseinanderzusetzen.

Relo4d schrieb:

diese funktion wird bei jedem durchlauf aufgerufen jedoch bricht das programm ab der 2ten if ab dann steht da "Ausnahmefehler bei 0x00BB1B9D in Baumso.exe: 0xC0000005: Zugriffsverletzung beim Lesen an Position 0xCDCDCDD5" dieser fehler tritt des öfteren auf und ich hab keine ahnung wie ich es anders machen soll [...]

Ohne mir deinen Code angesehen zu haben: Initialisiere mal alle Pointer im Konstruktor des Knotens mit nullptr (NULL). Wenn du dann etwas beim Dereferenzieren verbockst, solltest du eigentlich nur Meldungen bekommen, dass du versuchst einen Nullpointer zu dereferenzieren.

Da einige dieser Pointer offenbar nicht NULL sind (sonst sähe die Fehlermeldung anders aus), funktionieren deine NULL-Vergleiche auch nicht richtig und du wanderst wohl in Speicherbereiche, die nicht mehr zum Baum gehören.

Finnegan

Da wirst du wohl beim Aufbau schon was falsch gemacht haben.

Und wenn ich "struct node" sehe, würde ich sagen, das ist C in Reinkultur.

Danke, ich werds mal versuchen
tut mir leid wenn mein beitrag nicht der norm dieses forums entsprach, das war mein erster beitrag

Soo hab jetzt mal wieder dran gesessen und kriegs einfach nicht gescheit hin ^^

der code :

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

struct node {
	int value;
	char color;
	node *parent, *right, *left;
};

node *nil;
node *root;
node * setroot(node *n)
{
	if (n->parent != nil)
	{
		n = n->parent;
	}
	else
		setroot(n->parent);

	return n;
}
node *uncle(node *n)
{
	if (n == n->parent->right)
		return n->parent->parent->left;
	else
		return n->parent->parent->right;
}
node *grandpa(node *n)
{
	return n->parent->parent;
}
void rotateleft(node *n)
{
	node *tmp = (node *)malloc(sizeof(node));
	node *g = grandpa(n);
	if (n == n->parent->right)
	{
		tmp = n->parent;
		tmp->right = n->left;
		n->parent = n;
		n->parent = g;
		n->left = tmp;
	}
	else
	{
		*tmp = *g;
		n->parent->parent = n->parent;
		n->parent->color = 's';
		tmp->color = 'r';
		tmp->left = nil;
		n->parent->right = tmp;

	}

	free(g);
}
void rotateright(node *n)
{
	node *tmp = (node *)malloc(sizeof(node));
	node *g = grandpa(n);

	if (n == n->parent->left)
	{
		tmp = n->parent;
		tmp->left = n->right;
		n->parent = n;
		n->parent = g;
		n->right = tmp;
	}
	else
	{
		*tmp = *g;
		n->parent->parent = n->parent;
		n->parent->color = 's';
		tmp->color = 'r';
		tmp->left = nil;
		n->parent->left = tmp;
	}
	free(g);
}
void redblackbalance(struct node *n)
{
	if (n->parent == nil)
	{
		n->color = 's';
		return;
	}

	if (grandpa(n) != nil)
	{
		if (uncle(n)->color == 'r')
		{
			if (grandpa(n) != root)
				grandpa(n)->color = 's';
			else
				grandpa(n)->color = 'r';

			n->parent->color = 's';
			uncle(n)->color = 's';

		}
		if (uncle(n)->color = 's')
		{
			if (n->parent == grandpa(n)->left)
			{
				rotateleft(n);
			}
			if (n->parent == grandpa(n)->right)
			{
				rotateright(n);
			}
		}
	}

}
node *insert(int n, node *wurzel)
{
	node *tmp = nil;
	while (root)
	{
		if (root == nil)
		{
			root = (node *)malloc(sizeof(node));
			root->left = root->right = nil;
			root->left->parent = root->right->parent = root;
			root->value = n;
			root->color = 'r';
			root->parent = tmp;
			if (root->parent != nil)
			{
				if (root->value < root->parent->value)
					root->parent->left = root;
				else if (root->value > root->parent->value)
					root->parent->right = root;
			}
			break;
		}
		if (root->value == n)
			break;
		if (n >root->value)
		{
			tmp = root;
			root = root->right;
		}
		else if (root->value > n)
		{
			tmp = root;
			root = root->left;
		}
	}
	redblackbalance(root);

	wurzel = setroot(root);
	return wurzel;
}

void t_ausgabe(node *t,int tester)
{
	int i;
	if (t == nil)
		return;
	if (t->right != NULL)
	t_ausgabe(t->right, tester + 1);
	for (i = 0; i<tester; i++)
	{
		printf("\t");
	}
	printf("%d,%c", t->value, t->color);
	printf("\n");
	if (t->left != NULL)
	t_ausgabe(t->left, tester + 1);
}

void main()

{
	node *wurzel = (node*)malloc(sizeof(node));
	nil = (node*)malloc(sizeof(node));
	nil->value = NULL;
	nil->color = 's';
	root = nil;
	int tester = 0;

	int E = 'j';
	int v;

	while (E != 'N')
	{
		printf("Wert:");
		scanf("%d", &v);
		wurzel = insert(v,wurzel);
		root = wurzel;
		 t_ausgabe(wurzel, tester);
	}
}

das problem ist nun dass er nach dem ersten mal rotieren nur noch rotiert die schwarz tiefe ist nun auch nicht mehr gegeben >_< und sobald ich anfange im rechten teilbaum etwas einzufügen setzt er die wurzel gleich dem ersten stück im rechten teilbaum
würde mich freuen wenn jemand seine wertvolle zeit dafür opfert mir zu helfen ^^

liebe grüße Relo4d

C++ Forumbot

Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum C (alle ISO-Standards) verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

SeppJ

Das ist C, welches mit einem C++-Compiler übersetzt wurde. Um daraus richtiges C zu machen, sind folgende Änderungen nötig:

typedef struct node {
    int value;
    char color;
    struct node *parent, *right, *left;
} node;

Weiterhin ist stark empfohlen:

node *tmp = malloc(sizeof(node));  // ebenso alle anderen malloc

und

int main()

und

return 0; // am ende der main

Folgende Stellen sind verdächtig, was dir bereits der Compiler melden sollte, sofern du seine Warnungen aktivierst und beachtest:

nil->value = NULL;

Dem Wert wird ein Zeiger zugewiesen? Klingt nach Logikfehler.

if (uncle(n)->color = 's')

Das ist eine Zuweisung.

node *grandpa(node *n)
{
    return n->parent->parent;
}

Und wenn es keinen Großvater gibt?

Weiter muss man nicht groß analysieren, diese Fehler gilt es erst einmal zu beheben. Du machst dir natürlich selber das Leben extrem schwer, weil du globale Variablen nutzt. Das Nachvollziehen von Fehler ist dadurch unnötig schwer, dafür dass du ein paar Zeichen sparst, die du später doch wieder setzen musst, wenn du deinen Baum vernünftig benutzen möchtest. Weiterhin ist dein Baum nicht gut gekapselt, ein stärker objektorientierter Ansatz würde sich hier auszahlen.

PS: Seh ich jetzt erst:

int E = 'j';
    while (E != 'N')
    {
        scanf("%d", &v);

Buchstaben sind zwar auch nur Zahlen für den Computer, aber ich glaube, du nimmst das etwas zu wörtlich

uuh das sind ein paar viele hinweise danke !
aber in c++ existieren doch auch structs oder irre ich mich ?

ich versteh nicht warum die main einen wert zurückgeben soll bzw. warum sie vom typ int sein soll?

bevor ich den großvater setze wird erst getestet ob überhaupt einer existiert

lg Relo4d

SeppJ

Relo4d schrieb:

uuh das sind ein paar viele hinweise danke !
aber in c++ existieren doch auch structs oder irre ich mich ?

Ja, C++ kennt structs. Wie kommst du da drauf, dass sie nicht existieren? Lies meinen Beitrag noch einmal genau. Ich habe beschrieben, wie du aus deinem C++ richtiges C machst. Denn derzeit geht dein Code nur durch einen C++-Compiler, weil du (vermutlich unwissentlich) ein paar C++-Features genutzt hast. Aber es soll sich wohl um C handeln, denn richtiges C++ sähe ganz anders aus. Aus historischen Gründen kann man mit einem C++-Compiler zwar auch (nach einigen Änderungen^*) C übersetzen, aber so ganz kompatibel sind die Sprachen nicht mehr. Daher nicht empfehlenswert, C mit einem C++-Compiler zu übersetzen.

ich versteh nicht warum die main einen wert zurückgeben soll bzw. warum sie vom typ int sein soll?

Weil der Sprachstandard vorschreibst, dass main einen int zurück geben muss. Es darf zwar von der Implementierung unterstützt werden, es darf aber genau so gut undefiniertes Verhalten verursachen und das ist gar nicht gut.

^*: Beispielsweise sind deine Pointercasts in C++ nötig (abgesehen davon, dass man in richtigem C++ niemals malloc nutzen würde), in C hingegen verpönt. Die hast du wahrscheinlich nur gesetzt, um den Compiler zufrieden zu stellen. Daher habe ich in meinem letzten Beitrag empfohlen, diese Casts zu entfernen. Es gibt noch mehr Inkompatibilitäten (z.B. das Verhalten von nil->value = NULL; ), aber dies ist wohl die häufigst vorkommende und woran man leicht erkennt, wenn jemand einen C++-Compiler für C benutzt hat.

Warum gibt es in rotate malloc und free? Rotieren sollte doch ohne das Umkopieren von Daten möglich sein.