9 svar · 797 visningar · startad av SPiN
Hej där!
Jag sitter och filar på mina C/C++-kunskaper för tillfället, och arbetar med binära träd och C. Nu är det så att jag skulle behöva en metod för att balansera upp ett träd, och jag kommer ingenvart alls. Någon som kan förklara för mig hur jag bör göra, och kanske bidra med lite psuedokod? :)
Ponera att jag bygger mitt binära träd utifrån:
struct BinaryTree {
int mID;
struct BinaryTree* mLeft;
struct BinaryTree* mRight;
};
typedef struct BinaryTree Bt;
Jag lägger till en nod med:
void add( Bt** tree, Bt* node ) {
if( *tree == NULL )
*tree = node;
else if( (*tree)->mID > node->mID )
add( &(*tree)->mLeft );
else
add( &(*tree)->mRight );
}
Variabeln mID i BinaryTree har ett unikt värde.
Vad jag vet så finns det 2 sätt att balansera trädet, under körning, typ Red-Black tree som är det Javas Tree klasser använder, den andra metoden är att man helt enkelt lägger ner trädet i en sorterad array och sedan skapar det på nytt, då blir det perfekt balanserat.
För Red-Black kan du söka på internet, det finns mycket info om det.
/Viktor
Tack! Jag har sökt tidigare, men inte hittat något riktigt konkret och det lilla jag hittade förstod jag mig inte på. :OO :)
Tack igen. :)
Jo, jag vet om AVL. Men jag vill ju skriva mitt eget träd. :)
Ja? Du får ju skriva ditt egna AVL-träd istället för ett vanligt binärt träd.
Jag vet, det jag menade var att jag vill fortsätta med det träd jag redan har. Jag har redan skrivit en hel del, och vill inte anpassa mig efter AVL eftersom att det ändå går att lösa. :)
Jag förstår inte hur du menar. Om du inte vill ändra något i din datatyp så använd AVL-träd och räkna ut höjden dynamiskt. Det förstör komplexiteten men det fungerar.
Om du ska använda röd-svarta träd måste du ju lagra färgen på noden på något sätt. Eller har jag missförstått något?
Jag tänkte inte använda mig av Red Black-algoritmen heller, utan skyffla ner allt i en array och sedan sortera ut det på rätt ställen i trädet. På så sätt behöver jag endast skapa nya metoder och funktioner för att få det att fungera. Med AVL behöver jag ändra i mina redan existerande metoder/funktioner, samma med Red Black.
Ok, då förstår jag. Det kan nog vara en god idé, det är klurigt att rotera :)
