Drawing_Of_Binary_Tree/EfficiencyComparison.html at master · SoamyaAgrawal17/Drawing_Of_Binary_Tree · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
<!DOCTYPE HTML>
<head>
<title>Efficiency Comparison</title>
</head>

<body>
    <h1>Efficiency Comparision</h1>
<a href = "main.html">Main index</a>
    <a href = "EfficiencyComparison.html">Efficiency Comparision</a>
    <a href = "SpaceComparision.html">Space Comparision</a>
    <a href ="OutputComparison.html">Output Comparision</a>
<p><b>Analysis of both the algorithms and comparison of their performances in terms of efficiency.</b> </p>
<p><b>Paper-1</b></p>
<p><b><u>Tidy Drawings of Trees</u></b></p>
<p><b><u>CHARLES WETHERELL and ALFRED SHANNON</u></b></p>
<p>The algorithm  runs in linear time, taking several walks over the tree structure.</p>
<img src="Pictures/AlgorithmWS.png" />
<p><b>Fig. 1. Code snippet of Algorithm WS</b></p>
<p>Algorithm WS sets values of provisional xcoordinate and modifier using the above code and it is achieved by using postorder traversal which takes O(n) time where n denotes number of nodes.</p>
<img src="Pictures/AlgorithmWS1.png" />
<p><b>Fig. 2. Code snippet of Algorithm WS to assign final xcoordinate</b></p>
<p>Algorithm WS sets values of final xcoordinate using the above code and it is achieved by using preorder traversal which takes O(n) time where n denotes number of nodes.</p>
<p>To draw circles (denoting the vertex) and lines (denoting the edges) preorder traversal is used which takes O(n) time and to draw lines and circles,midpoint algorithm and Bresenham's line drawing algorithm is used respectively,which takes constant time O(1).</p>
<p>To assign ycoordinate to each node, height function is defined which takes O(log(n)) time in average case and O(n) in worst case.</p>
<p>To insert nodes in binary tree insert function is defined which takes O(log(n)) time in average case and O(n) in worst case.</p>
<p>So, time complexity comes out to be O(n^2) in worst case and O(nlog(n)) in average case.</p>
<img src="Pictures/TimeAnalysis1.png" />
<p><b>Fig. 3. Graph showing time taken by Algorithm WS in seconds on y-axis vs input size (number of nodes) using library matplotlib of python.</b></p>
<br><br><br>

<p><b>Paper-2</b></p>
<p><b><u>Tidier Drawings of Trees</u></b></p>
<p><b><u>EDWARD M.REINGOLD and JOHN S. TILFORD</u></b></p>
<p>The algorithm does not appear to be cost effective because it must examine the contour of the subtrees of every node in the tree. However, the requirement that scanning must proceed only to the depth of the shorter subtree of each node makes the running time linear in the number of nodes in the tree and hence comparable to that of Algorithm WS.</p>
<img src="Pictures/AlgorithmTS0.png" />
<p><b>Fig. 4. Code snippet of Algorithm TR to assign relative xcoordinate</b></p>
<p> The time required by Algorithm TR is completely determined by the while loop because SETUP is executed exactly once per node of the tree.
The worst case is a complete binary tree for which the loop is executed about n(T) - lg n(T) times,
where n(T) denotes the number of nodes binary tree at node T contains; its height h(T) is the number of nodes on the longest path from the root to a leaf.</p>
<img src="Pictures/AlgorithmTS1.png" />
<p><b>Fig. 5. Code snippet of Algorithm TR to assign absolute xcoordinate</b></p>
<p>Algorithm TR sets values of final xcoordinate using the above code and it is achieved by using preorder traversal which takes O(n) time where n denotes number of nodes.</p>
<p>To draw circles (denoting the vertex) and lines (denoting the edges) preorder traversal is used which takes O(n) time and to draw lines and circles,midpoint algorithm and Bresenham's line drawing algorithm is used respectively,which takes constant time O(1).</p>
<p>To assign ycoordinate to each node, height function is defined which takes O(log(n)) time in average case and O(n) in worst case.</p>
<p>To insert nodes in binary tree insert function is defined which takes O(log(n)) time in average case and O(n) in worst case.</p>

<img src="Pictures/TimeAnalysis2.png" />
<p><b>Fig. 6. Graph showing time taken by Algorithm TR in seconds on y-axis vs input size (number of nodes) using library matplotlib of python.</b></p>
<p>It is imperative to note, that the time graphs drawn above are the 'actual' practically realised times. The values were all measured under similar cirucumstances for a given Algorithm. Hence, even if the initial parameters may vary with some discrepancies, the overall shape and nature of the curve persists. The graphical realisation was done, using file I/O of C, to output the times to a local file. The FILE I/O's overhead wasn't considered while making the time computations. And the subsequent output of the file, is taken as input by a python script, which uses the matplotlib library, to graph the curves. The inputs were randomly generated from the C standard library's functions, and were taken to be less than 1000 in an effort to curb the variance of their output.</p>
</body>
</html>