Efficient Tree Structure Hierarchy Rebuild

Question

I'm having a tree structure like this:

1 ABC

1.1 DEF

1.1.2 GHI

1.2 JKL

1.2.1 MNO

2 PQR

2.1

... with no limits on the depth and length of each level. Now what happens is that I take out some of the elements all around the tree structure and in the end I want to have a proper, restructured hierarchy numbering.

How do you usually re-sort & apply proper hierarchy numbering in the least amount of work in such a case? This is a somewhat basic use case, but I'm looking for some room for improvement.

Answer 1

I suppose that you are keeping both number and the text in the same value variable.

The simplest thing you could possibly do is to:

1. Separate that into two variables: number and text
2. Whenever you are swapping two tree nodes (i.e. during sorting) swap just text values and keep the number values where they are.
3. Whenever you are adding new element as the last subelement, just use the previousLastElement.number + 1
4. Whenever you print out the elements number reversly append all its parents numbers separated by dot.

The only remaining complexity now is when you insert elements, where you would have to "push" the other elements' numbers after that one (but only on that one level), or when you remove elements, when you would have to pull them.

Answer 2

You could use a priority queue like a self-balancing tree.