Recursive function - H tree

Nov. 29, 2017

Introduction

It is the first time I practiced to write down the numbers for a H-Tree using given center value and length and depth. I chose to follow the test case with depth 3 and went over the detail to discuss the algorithm.

I tried to do something different this time. I chose to do different on algorithm analysis.

Algorithm analysis

Here is my transcript to do analysis of algorithm. I am working on presentation skills, make the test case easy to follow.

Given depth = 3, draw H tree. First depth is 3, one H tree; next depth is 2, with 4 trees centered on corners of H. So time complexity can be analyzed by the number of trees, here is the formula:

1 + 4 + 4^2 +... + 4 ^(depth -1) = (4^depth)/( 4 - 1).

Each H-tree has 3 lines to draw, O(1) to draw a line, and then time complexity is O(4^depth).

Next work on H-tree three lines, given center (2, 0), length = 4. Draw the graph below, the four corners clockwise from top left are (0, 2), (4, 2), (4, -2), (0, -2).

    0  1  2  3  4
2  |               |
1  |               |
0  | ---------- |
-1 |               |
-2 |               |


C# code is here.