AVL tree

2016-Jul-10, Sunday 20:44
mindstalk: (YoukoYouma)
[personal profile] mindstalk
For a long time, self-balancing trees had seemed like magic to me. Earlier this year I put my mind to figuring them out, and on my own came up with the idea of a weight-balanced tree. With a bit of peeking, I then moved on to a height-balanced tree, pretty much an AVL tree. Then I started coding one in pure C, for Real Programmer (TM) cred.

Stage one, achieved some months ago, fulfilled the basic criterion: you could feed it an increasing sequence of keys, and get a beautifully balanced tree back out. Woo! It had problems, though. Most obviously, I concentrated on the balancing part first, so got heights on the fly via a function rather than from cached values. Not exactly computationally efficient. Less obviously, I had a clever-seeming tree-rotation function I'd come up with: "to rotate right: insert root value to the right, copy rightmost left value into root, delete same value from the left tree." Elegant, but O(log(N)), when there are actually O(1) rotations available.

I went back to the project this evening, and got the faster rotations working. It took longer than I expected, because when you do rotations that way, there's complexity: 1->2->3 can be rotated left, but 1->3->2 needs a rotation right (on 3->2) then left, to come out balanced. Turns out that my slower rotation did the correct thing in both cases, so simply replacing my rotate functions wasn't working until I added more logic. Grumble grumble.

I still don't have heights cached, and the whole thing feels like an unholy mess of pointer manipulations (especially with parent points in the tree.) But, progress!

January 2019

678 910 1112
131415 16171819

Expand Cut Tags

No cut tags

Style Credit

Most Popular Tags