AVL-Baum Code Problem

[FlashBurn]

Ich habe also nen AVL-Bau implementiert, aber irgendwie funktioniert dieser nicht richtig.

Erstmal der Code:

#define AVL_LEFT 1
#define AVL_RIGHT 0

#define AVL_MAX_LEVEL 28

struct avlDebugNode_t {
	struct avlDebugNode_t *left;
	struct avlDebugNode_t *right;
	int balance;
	uint32t val;
	char *name;
};

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL], *new= newNode;
	int level= 0, res;
	uint8t levelDirection[AVL_MAX_LEVEL];

	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;

	if(likely(node)) {
		while(1) {
			levelNode[level]= node;
			res= (int)(node->val - newNode->val);

			if(likely(res)) {
				if(res > 0) {
					levelDirection[level]= AVL_LEFT;

					if(likely(node->left))
						node= node->left;
					else
						break;
				} else {
					levelDirection[level]= AVL_RIGHT;

					if(likely(node->right))
						node= node->right;
					else
						break;
				}
			} else {
				newNode->left= (struct avlDebugNode_t *)1;
				newNode->right= (struct avlDebugNode_t *)1;

				return startNode;
			}

			level++;
		}

		while(likely(level >= 0)) {
			node= levelNode[level];

			if(levelDirection[level] == AVL_LEFT) {
				node->left= new;

				if(node->balance == -1) {
					if(node->left->balance == 1)
						node= avlRotateLeftRight(node);
					else
						node= avlRotateRight(node);
				} else {
					node->balance--;

//					if(!node->balance)
//						return startNode;
				}
			} else {
				node->right= new;

				if(node->balance == 1) {
					if(node->right->balance == -1)
						node= avlRotateRightLeft(node);
					else
						node= avlRotateLeft(node);
				} else {
					node->balance++;

//					if(!node->balance)
//						return startNode;
				}
			}

			new= node;
			level--;
		}

		return node;
	} else {
		return newNode;
	}
}

struct avlDebugNode_t *avlRotateLeft(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->right;

	node->right= newNode->left;
	newNode->left= node;

	node->balance--;
	newNode->balance--;

	return newNode;
}

struct avlDebugNode_t *avlRotateLeftRight(struct avlDebugNode_t *node) {
	node->left= avlRotateLeft(node->left);

	return avlRotateRight(node);
}

struct avlDebugNode_t *avlRotateRight(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->left;

	node->left= newNode->right;
	newNode->right= node;

	node->balance++;
	newNode->balance++;

	return newNode;
}

struct avlDebugNode_t *avlRotateRightLeft(struct avlDebugNode_t *node) {
	node->right= avlRotateRight(node->right);

	return avlRotateLeft(node);
}

So nun zu den Problemen. Er scheint über das maximale Level von 28 hinauszugehen, da der Stack der aufrufenden Funktion zerstört wird. Desweiteren kann es nicht sein, das wenn etwas über 200 Einträge in dem Baum sind, er immernoch nach der 1. While-Schleife im 3.-5. Level etwas einfügt.

Die 4 Auskommentierten Zeilen scheinen das Problem geringer zu machen, aber das Einfügen im 3.-5. Level nach etwas über 200 Einträgen kommt trotzdem noch.

Wer kennt sich mit dem AVL-Baum aus und kann mir sagen wo das Problem liegen könnte?

[FlashBurn]

Scheinbar kann mir keiner helfen. Ich habe schon 3 Fehler gefunden, einmal im Balancing Code, einmal dass das Kind-Node nicht an das Elternteil weitergegeben wird wenn die Balance auf 0 geht und einmal das ich abbrechen muss, sobald irgend eine Balance (der aktuellen Node) auf 0 gesetzt wird.

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL], *new= newNode;
	int level= 0, res;
	uint8t levelDirection[AVL_MAX_LEVEL], finished= 0;

	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;

	if(likely(node)) {
		while(1) {
			levelNode[level]= node;
			res= (int)(node->val - newNode->val);

			if(likely(res)) {
				if(res > 0) {
					levelDirection[level]= AVL_LEFT;

					if(likely(node->left))
						node= node->left;
					else
						break;
				} else {
					levelDirection[level]= AVL_RIGHT;

					if(likely(node->right))
						node= node->right;
					else
						break;
				}
			} else {
				newNode->left= (struct avlDebugNode_t *)1;
				newNode->right= (struct avlDebugNode_t *)1;

				return startNode;
			}

			level++;
		}

		while(likely(level >= 0)) {
			node= levelNode[level];

			if(levelDirection[level] == AVL_LEFT) {
				node->left= new;

				if(unlikely(finished))
					return startNode;

				if(node->balance == -1) {
					if(node->left->balance == 1) {
						node= avlRotateLeftRight(node);
					} else {
						node= avlRotateRight(node);
					}
				} else {
					node->balance--;
				}
			} else {
				node->right= new;

				if(unlikely(finished))
					return startNode;

				if(node->balance == 1) {
					if(node->right->balance == -1) {
						node= avlRotateRightLeft(node);
					} else {
						node= avlRotateLeft(node);
					}
				} else {
					node->balance++;
				}
			}

			if(unlikely(!node->balance))
				finished= 1;

			new= node;
			level--;
		}

		return node;
	} else {
		return newNode;
	}
}

struct avlDebugNode_t *avlRotateLeft(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->right;

	node->right= newNode->left;
	newNode->left= node;

//	node->balance--;
	node->balance-= 1 - MAX(newNode->balance,0);
//	newNode->balance--;
	newNode->balance-= 1 + MIN(node->balance,0);

	return newNode;
}

struct avlDebugNode_t *avlRotateRight(struct avlDebugNode_t *node) {
	struct avlDebugNode_t *newNode= node->left;

	node->left= newNode->right;
	newNode->right= node;

//	node->balance++;
	node->balance+= 1 - MIN(newNode->balance,0);
//	newNode->balance++;
	newNode->balance+= 1 + MAX(node->balance,0);

	return newNode;
}

Nun habe ich den Code wo ich ihn eigentlich benutze auch geändert, habe aber die Debugmeldungen angelassen und leider habe ich immernoch das Gefühl das er nicht funktioniert.

Also das "Level" ist ja gewissermaßen die Höhe (beginnt halt bei 0).

So ich füge 180 Werte in den Baum ein und da passiert nun folgendes mit den Leveln:

...;;4;;7;;3;;10;;9;;10;;9;;9;;3;;8;;9;;12;;...

Und das geht ja schlecht, ich meine wenn das höchste Level was er bisher erreicht hat 7 ist, dann kann er nicht mit einmal 2 Level überspringen und im 10. Level einfügen, oder!? Das selbe dann nochmal mit dem 12. Level.

Was mich auch ein wenig verwundert, ist es überhaupt möglich bei 180 Werten in einem AVL-Baum, das er bis ins 17. Level kommt?

Was mich auch stört ist, das mein Code es schafft das die Höhenunterschiede größer als 1 sind. Denn wenn ich schon was im 10. Level eingefügt habe, dann kann ich doch nicht 3 Einfügeoperationen später was im 3. Level einfügen, da dürfte überhaupt nichts mehr frei sein!

Es wäre also sehr hilfreich, wenn mich jemand der Ahnung vom AVL_Baum hat, mal in die richtige Richtung schickt

[FlashBurn]

Ok, noch einen Fehler das Balancing betreffend gefunden und korrigiert, aber immernoch nicht perfekt

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL], *new= newNode;
	int level= 0, res;
	uint8t levelDirection[AVL_MAX_LEVEL], finished= 0;

	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;

	if(likely(node)) {
		while(1) {
			levelNode[level]= node;
			res= (int)(node->val - newNode->val);

			if(likely(res)) {
				if(res > 0) {
					levelDirection[level]= AVL_LEFT;

					if(likely(node->left))
						node= node->left;
					else
						break;
				} else {
					levelDirection[level]= AVL_RIGHT;

					if(likely(node->right))
						node= node->right;
					else
						break;
				}
			} else {
				newNode->left= (struct avlDebugNode_t *)1;
				newNode->right= (struct avlDebugNode_t *)1;

				return startNode;
			}

			level++;
		}

		while(likely(level >= 0)) {
			node= levelNode[level];

			if(levelDirection[level] == AVL_LEFT) {
				node->left= new;

				if(unlikely(finished))
					return startNode;

				node->balance--;

				if(node->balance == -2) {
					printf("balance: ");

					if(node->left->balance == 1) {
						node= avlRotateLeftRight(node);
					} else {
						node= avlRotateRight(node);
					}
				}
			} else {
				node->right= new;

				if(unlikely(finished))
					return startNode;

				node->balance++;

				if(node->balance == 2) {
					printf("balance: ");

					if(node->right->balance == -1) {
						node= avlRotateRightLeft(node);
					} else {
						node= avlRotateLeft(node);
					}
				}
			}

			if(unlikely(!node->balance))
				finished= 1;

			new= node;
			level--;
		}

		return node;
	} else {
		return newNode;
	}
}

Der Code überspring jetzt zwar auch auch noch ein Level, aber immerhin nicht mehr 2 und das max. Level ist jetzt auch nur noch 11, aber er fügt immernoch in Level ein, wo eigentlich gar nichts mehr frei sein darf/kann! Ich komme der Lösung also näher

[FlashBurn]

So endlich funktioniert der Code:

struct avlDebugNode_t *avlInsert(struct avlDebugNode_t *startNode, struct avlDebugNode_t *newNode) {
	struct avlDebugNode_t *node= startNode, *levelNode[AVL_MAX_LEVEL], *new= newNode;
	int level= 0;
	uint8t levelDirection[AVL_MAX_LEVEL], finished= 0;

	newNode->left= 0;
	newNode->right= 0;
	newNode->balance= 0;

	if(likely(node)) {
		while(1) {
			levelNode[level]= node;

			if((int)(node->val - newNode->val) > 0) {
				levelDirection[level]= AVL_LEFT;

				if(likely(node->left))
					node= node->left;
				else
					break;
			} else {
				levelDirection[level]= AVL_RIGHT;

				if(likely(node->right))
					node= node->right;
				else
					break;
			}

			level++;
		}

		while(likely(level >= 0)) {
			node= levelNode[level];

			if(levelDirection[level] == AVL_LEFT) {
				node->left= new;

				if(unlikely(finished))
					return startNode;

				node->balance--;

				if(node->balance == -2) {
					if(node->left->balance == 1)
						node= avlRotateLeftRight(node);
					else
						node= avlRotateRight(node);
				}
			} else {
				node->right= new;

				if(unlikely(finished))
					return startNode;

				node->balance++;

				if(node->balance == 2) {
					if(node->right->balance == -1)
						node= avlRotateRightLeft(node);
					else
						node= avlRotateLeft(node);
				}
			}

			if(unlikely(!node->balance))
				finished= 1;

			new= node;
			level--;
		}

		return node;
	} else {
		return newNode;
	}
}

struct avlDebugNode_t *avlRotateLeft(struct avlDebugNode_t *root) {
	struct avlDebugNode_t *newRoot= root->right;

	root->right= newRoot->left;
	newRoot->left= root;

//	root->balance-= (1 - MAX(newRoot->balance,0));
	root->balance= root->balance - 1 - MAX(newRoot->balance,0);
//	newRoot->balance-= (1 + MIN(root->balance,0));
	newRoot->balance= newRoot->balance - 1 + MIN(root->balance,0);

	return newRoot;
}

struct avlDebugNode_t *avlRotateLeftRight(struct avlDebugNode_t *node) {
	node->left= avlRotateLeft(node->left);

	return avlRotateRight(node);
}

struct avlDebugNode_t *avlRotateRight(struct avlDebugNode_t *root) {
	struct avlDebugNode_t *newRoot= root->left;

	root->left= newRoot->right;
	newRoot->right= root;

//	root->balance+= (1 - MIN(newRoot->balance,0));
	root->balance= root->balance + 1 - MIN(newRoot->balance,0);
//	newRoot->balance+= (1 + MAX(root->balance,0));
	newRoot->balance= newRoot->balance + 1 + MAX(root->balance,0);

	return newRoot;
}

struct avlDebugNode_t *avlRotateRightLeft(struct avlDebugNode_t *node) {
	node->right= avlRotateRight(node->right);

	return avlRotateLeft(node);
}

Jetzt hätte ich nur eine Frage, ich habe bei den Rotationen jeweils 2 Zeilen auskommentiert (die Kurzschreibweise) und habe es ganz genau hingeschrieben. Mich würde jetzt interessieren wie die Kurzschreibweise dafür aussieht. Denn ich dachte immer er macht aus:

foo+= (bar + bar);

dann:

foo= foo + (bar + bar);

Aber anscheinend ja nicht, denn wenn ich meine Kurzschreibweise nehme, dann funktioniert es nicht oder habe ich da irgendwie einen Denkfehler drin?

[nwp2]

+= tut genau was du geschrieben hast.
Dein -= allerdings nicht.

root->balance -= 1 - MAX(newRoot->balance,0);
//bedeutet
root->balance = root->balance - (1 - MAX(newRoot->balance,0));
//oder
root->balance = root->balance - 1 + MAX(newRoot->balance,0);
//aber nicht
root->balance= root->balance - 1 - MAX(newRoot->balance,0);

Was tun denn likely() und unlikely()?

Den Rest überblicke ich gerade nicht wirklich.

[FlashBurn]

"likely"und "unlikely" sind Makros für GCC damit man ihm sagen kann welcher Fall wahrscheinlicher ist (zwecks Optimierung):

#define likely(x)	__builtin_expect(!!(x), 1)
#define unlikely(x)	__builtin_expect(!!(x), 0)

Achso, da hätte ich natürlich auch alleine drauf kommen können, das heißt ja praktisch "* -1". Werd ich dann nachher gleich mal ausprobieren. Danke!

nwp2 schrieb:

Den Rest überblicke ich gerade nicht wirklich.

Weil der Code gar nicht kommentiert ist oder weil du mit dem AVL-Baum sowieso nicht viel anfangen kannst?

Ich kann dir zumindestens sagen, das die 1. while Schleife die Stelle im Baum sucht, wo die neue Node eingefügt werden kann und die 2. while Schleife ist dann der Rückweg, wo eventuell eine Korrektur am Baum gemacht wird.

[FlashBurn]

Ich dachte ich nutze dieses Thema mal um eine kleine Diskussion zum AVL-Baum zu starten.

Mir geht es um gewisse Optimierungen, erstmal nur die, die den Algo an sich betreffen (und nichts mit "Programmier-Tricks" zu tun haben).

Beim Einfügen kann ich das "Hoch-Laufen" des Baumes beenden, wenn sich die Balance des aktuellen Knotens auf 0 verändert hat.

Beim Löschen bin ich mir nicht sicher, aber ich habe mal gehört das man da das "Hoch-Laufen" beenden kann, wenn sich die Balance auf 1 oder -1 (von 0) verändert hat. Stimmt das?
Desweiteren ist es von Vorteil das man beim Löschen, wenn mind. 1 Kind vorhanden ist, den zu löschenden Knoten gegen einen aus dem tieferen Teilbaum ersetzt (entweder das kleinste Kind aus dem rechten Teilbaum oder das größte Kind aus dem linken Teilbaum).

Fällt jemandem noch mehr solcher Optimierungen ein oder das eine davon falsch ist?

[cooky451]

http://www.c-plusplus.net/forum/186643

Beste Grüße

[FlashBurn]

Ich kenne den Artikel, aber es dort wird ja nur der AVL-Baum allgemein erklärt, nicht wie man bestimmte Sachen noch optimieren kann (am Algo und halt Programmier-Tricks).