insertTopDown(index: Int, instance: N)
Indicates that instance should be inserted as a child to current at index. An applier
should insert the node into the tree either in insertTopDown or insertBottomUp, not both.
The insertTopDown method is called before the children of instance have been created and
inserted into it. insertBottomUp is called after all children have been created and
inserted.
Some trees are faster to build top-down, in which case the insertTopDown method should
be used to insert the instance. Other tress are faster to build bottom-up in which case
insertBottomUp should be used.
To give example of building a tree top-down vs. bottom-up consider the following tree,
R
|
B
/ \
A C
where the node B is being inserted into the tree at R . Top-down building of the tree
first inserts B into R , then inserts A into B followed by inserting C into B`.
For example,
1 2 3
R R R
| | |
B B B
/ / \
A A C
A bottom-up building of the tree starts with inserting A and C into B then inserts
B tree into R .
1 2 3
B B R
| / \ |
A A C B
/ \
A C
To see how building top-down vs. bottom-up can differ significantly in performance
consider a tree where whenever a child is added to the tree all parent nodes, up to the root,
are notified of the new child entering the tree. If the tree is built top-down,
R is notified of B entering.
B is notified of A entering, R is notified of A entering.
B is notified of C entering, R is notified of C entering.
for a total of 5 notifications. The number of notifications grows exponentially with the
number of inserts.
For bottom-up, the notifications are,
B is notified A entering.
B is notified C entering.
R is notified B entering.
The notifications are linear to the number of nodes inserted.
If, on the other hand, all children are notified when the parent enters a tree, then the
notifications are, for top-down,
B is notified it is entering R .
A is notified it is entering B .
C is notified it is entering B .
which is linear to the number of nodes inserted.
For bottom-up, the notifications look like,
A is notified it is entering B .
C is notified it is entering B .
B is notified it is entering R , A is notified it is entering R ,
C is notified it is entering R .
which exponential to the number of nodes inserted.
|