balance barnary trees

jeg plejer at lave:
  binært træ -> array -> binært træ
men jeg er ikke datalog så ...

Hvis man bruger et Splay tree, er det slet ikke nødvendigt at balancere træet - splay trees er binære træer, der løbende "balancerer" sig selv. Sagt på en simpel måde, ændres rod-noden løbende, således at den node man sidst havde fat i bliver sat som rod-node. Samtidig flyttes den ene side af den nye rod-nodes børn til den forhenværende rod-node.

Hvis f.eks. du tilgår en node på venstre side af den aktuelle rod-node, sættes denne node som rod-node, hvorefter børnene på den højre side flyttes til den forhenværende rod-nodes venstre side. Ved ikke lige om det er til at forstå :-)

Resultatet er, at træet løbende holder sig nogenlunde balanceret, hvilket i længden er langt billigere end at skulle balancere et helt træ på en gang.

eller du kan bruge et red-black tree

her er en demo samt source code til den
http://www.ececs.uc.edu/~franco/C321/html/RedBlack/redblack.html

jeg har skrevet en raport om bl.a red-black og binære søgetræer men den har ikke en direkte implementation.. den kigger mere på properties, algortimen, tidskompleksitet m.m men sig til hvis du vil set det.

jeg kan anbefale dig
Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms, 2nd edition, MIT Press, 2001.
Hvis du vil kigge nærmere på forskellige træer.

Treap er også en mulighed. Der er en artikkel her omkring implementering af en Treap i Java

http://www.nada.kth.se/~snilsson/public/papers/treap/intro.html

Treap bruger en randomized priority queue til at balancere sig selv.