AVL Tree

Ruby
1

Hello!

I have a quick question about the AVL tree. Isn’t this a lot like the
Rope quiz? When I wrote my Rope entry, I made it into a self-
balancing tree like this (although I forsaked all heap properties).

Hmm. Maybe I need to rewrite my Rope entry.

~ Ari
English is like a pseudo-random number generator - there are a
bajillion rules to it, but nobody cares.

2

On Dec 14, 2007 9:37 PM, thefed [email protected] wrote:

Hello!

I have a quick question about the AVL tree. Isn’t this a lot like the
Rope quiz? When I wrote my Rope entry, I made it into a self-
balancing tree like this (although I forsaked all heap properties).
I have seen the solutions using AVL tree balancing for ropes but I
guess that the original balancing algorithm is better adapted to
most applications of Ropes. But I wonder too.

Hmm. Maybe I need to rewrite my Rope entry.
I still need to write my entry…
R.
–

http://ruby-smalltalk.blogspot.com/

All truth passes through three stages. First, it is ridiculed. Second,
it is violently opposed. Third, it is accepted as being self-evident.
Schopenhauer (attr.)

3

On Dec 14, 2007, at 2:37 PM, thefed wrote:

I have a quick question about the AVL tree. Isn’t this a lot like
the Rope quiz? When I wrote my Rope entry, I made it into a self-
balancing tree like this (although I forsaked all heap properties).

Some people did use AVL balancing in their ropes, but I consider the
binary tree to be a more general data structure.

Beyond that, this quiz is far more about the build strategy than the
task itself.

James Edward G. II

4

On Dec 15, 2007, at 8:23 AM, Rick DeNatale wrote:

Beyond that, this quiz is far more about the build strategy than the
task itself.

I hope this is taken the right way, but as I think of this quiz, I’m
afraid that picking a particular data structure/algorithm like an AVL
tree isn’t the best way to do that.

I’m sure I make plenty of mistakes. This could be one of them.

However, when there are no submissions, you’re stuck with my ideas for
better and worse. I like to try new things from time to time.

I also don’t see anything wrong with TDDing an algorithm. Besides
that, there should be a heck of a lot more interface work than there
is AVL rotations in our tree library.

James Edward G. II

5

On 12/14/07, James G. [email protected] wrote:

task itself.
I hope this is taken the right way, but as I think of this quiz, I’m
afraid that picking a particular data structure/algorithm like an AVL
tree isn’t the best way to do that.

The ping-pong programming comes out of test driven design, which is a
way to derive a design iteratively by refining external requirements.

In this quiz, we have the goal of implementing a particular algorithm,
which isn’t realy the same thing at all.

A more general task, such as building a lookup tree, or a balanced
lookup tree would probably explore the build strategy better, perhaps
with the quizmaster stepping in at times to introduce one or more new
requirements, but it’s too late for that.

Just my opinion.

Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/