主題 
Tree Algorithm Seminar 
主辦單位 
演算法與計算理論學會 
協辦單位 
中華大學資訊工程系 
時間 
2016年11月15日(二)09:00~12:00 
地點 
中華大學創新廳(工程一館) 
流程 
9:00~9:50 Talk 1 The red black tree is an elegant data structure of balanced binary search tree adopted in many applications. The tree performs searching, insertion and deletion operations in O(log n) time, where n is the number of tree nodes. In this talk, we shall introduce the basic properties and operations of the red black tree. Moreover, examples are also provided in this talk to illustrate the detailed steps pf operations on red black trees.
Talk 2 11:00~11:50 Talk 3 In a dynamic graph problem one would like maintain a data structure to answer a certain query, such that when a simple change is made, e.g. the insertion or deletion of an edge, the data structure can be updated faster than recomputing from scratch. Efficient solutions to this problem have numerous applications, particularly in algorithms for fully dynamic tree problems. In a dynamic tree problem, we may have a free tree (i.e., trees that are unrooted and undirected). If the tree dynamically changes over time by edge insertions and deletions all these changes have to be reflected to certain property. For example, the longest path may be different if the tree is changed. The question is how to deal with these changes efficiently. A data structure, called toptrees, can be used to provide an O(log n) time solution when facing these changes. Top trees are a dynamic selfadjusting data structure that was proposed by Alstrup et al. (S. Alstrup, J. Holm, K. D. Lichtenberg, and M. Thorup, Maintaining information in fully dynamic trees with top trees, ACM Trans. Algorithms, 1(2):243–264, 2005) for maintaining information in a fullydynamic forest. A top tree R is an ordinary binary tree with a root. It is used to represent a free tree T with defined information that some tree algorithm works with. The structure of R consists of clusters. The edges of T form basic clusters and two clusters connected through a common vertex create other cluster. So the R records a way of clusters connecting into one root cluster that represents whole T. Each cluster holds information of appropriate part of T. Therefore, when the edges of T are changed, top tree R is also changed so that certain property is changed accordingly in O(log n) time. As a result, any edge insertion or deletion can be done in an efficient manner.
