---
title: "Balansera ett binärt träd"
type: "forum-thread"
url: "https://www.webforum.nu/amne/c-cpp/89698-balansera-ett-binärt-träd"
topic: "C/C++"
topic_url: "https://www.webforum.nu/amne/c-cpp"
author: "SPiN"
published: "2003-11-05T12:35:27.000Z"
updated: "2003-11-05T16:31:39.000Z"
replies: 9
views: 830
page: 1
pages: 1
language: "sv-SE"
site: "webForum — webforum.nu"
rights: "Upphovsrätten till varje inlägg tillhör dess författare."
attribution: "Citera som: webForum, https://www.webforum.nu/amne/c-cpp/89698-balansera-ett-binärt-träd"
---

# Balansera ett binärt träd

## #1 — SPiN, 2003-11-05T12:35Z

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.

Permalänk: https://www.webforum.nu/p/89698

## #2 — Viktor, 2003-11-05T12:42Z

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

Permalänk: https://www.webforum.nu/p/1198107

## #3 — SPiN, 2003-11-05T12:55Z

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. :)

Permalänk: https://www.webforum.nu/p/1198112

## #4 — Gein, 2003-11-05T13:02Z

Du kan använda dej av AVL Tree vilket är ett balanserat binärt sökträd. Googla efter AVL tree eller [kolla här](http://www.kraml.at/georg/avltree/). Denna sida förklarar lite hur AVL Tree fungerar och den verkar även ha exempelkod. :)

Permalänk: https://www.webforum.nu/p/1198116

## #5 — SPiN, 2003-11-05T13:06Z

Jo, jag vet om AVL. Men jag vill ju skriva mitt eget träd. :)

Permalänk: https://www.webforum.nu/p/1198119

## #6 — Gein, 2003-11-05T13:10Z

Ja? Du får ju skriva ditt egna AVL-träd istället för ett vanligt binärt träd.

Permalänk: https://www.webforum.nu/p/1198123

## #7 — SPiN, 2003-11-05T13:15Z

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. :)

Permalänk: https://www.webforum.nu/p/1198125

## #8 — juventus1, 2003-11-05T13:37Z

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?

Permalänk: https://www.webforum.nu/p/1198136

## #9 — SPiN, 2003-11-05T13:51Z

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.

Permalänk: https://www.webforum.nu/p/1198143

## #10 — juventus1, 2003-11-05T16:31Z

Ok, då förstår jag. Det kan nog vara en god idé, det är klurigt att rotera :)

Permalänk: https://www.webforum.nu/p/1198219

---

Tråden på webben: https://www.webforum.nu/amne/c-cpp/89698-balansera-ett-binärt-träd