3

Algorithms class was a such a long time ago and I can't remember the name of the algorithm to balance an acyclic graph.

Let's start with a graph that looks like this:

 1 | 2 | 3 / \ 4 7 / \ | 5 6 8

The solution to balancing this out would be:

 2 3 / \ / | \ 1 3 2 4 7 / \ => / / \ | 4 7 1 5 6 8 / \ | 5 6 8

You rotate until the you have a root node whose branch's are the same length and your tree is at a minimum height.

What algorithm am I describing?

Improve this question
5

1 Answer 1

Reset to default
2

You might want to provide some more details in your description. Also, the example you give does not seem to be consistent (e.g. node 3 suddenly takes three children), whereas all other nodes seem to maintain at most two children.

Based on the little detail you provide, your rotation operations are similar to what's described in AVL tree rotations. See e.g. the wikipedia page for more details.

Improve this answer

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.