樹結構佈局最佳化之探討

Abstract

在計算機科學中，樹是一個被廣泛使用的資料結構。樹的佈局問題即是計 算該樹中每個節點的座標。然而佈局必須滿足特定的審美標準與使用最小 的佈局空間。不同的審美標準將會有不同型態的樹結構佈局產生。本論文 提出二種佈局演算法。每一個演算法符合各自的審美標準。第一個演算法 ，我們採用由上到下階層式的處理方式。其時間複雜度是O(n*n)，n是該 樹的節點個數。我們證明經由此演算法所產生出的佈局必定有最小寬度。 第二個演算法藉由置換某些特定的點來減少佈局的總寬度。在這個演算法 中，我們僅允許葉節點與其兄弟節點間的相對順序是可被置換的。其時間 複雜度是 O(width*n)，width 是樹寬，n是該樹的節點個數。而其空間複 雜度是 O(width*width)。當每一階層的最小成本路徑是唯一將會產生最 小寬度的佈局。我們討論最小成本路徑不是唯一的情況。最後我們討論當 所有點皆可被置換時所產生的最小寬度佈局。 Trees are a common data structure widely used in computer science. The tree layout problem is to compute the coordinates of nodes of a tree. A layout must satisfy certain aesthetic standards and use minimum layout space. Different aesthetic standards will produce different styles of tree layouts. This thesis proposes two layout algorithms. The layout algorithms satisfy their respective aesthetic standards. The first algorithm is different from others [1]-[6] in that we process a tree from root to leaf in a level-by-level approach. It takes O( n*n) time, n is the number of nodes of a tree. We show that the layout calculated by the algorithm has minimum width. The second algorithm reduces the width of tree layouts by re- arranging certain nodes. We only allow that the relative ordering of a leaf nodes and its sibling nodes may be re- arranged. The time complexity is O(width*n), where width is the width of a tree, and n is the number of nodes of a tree. It also needs O(width*width) space. The layout calculated by the algorithm has the minimun width when the least-cost path on each level is unique. We discuss the situation when there is more than one the least-cost path. We also discuss a layout of the minimum width if all sibling nodes may be re-arranged in the end.