![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Entry tags:
AVL tree
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!
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!