演算法與計算理論學會

Association of Algorithm and Computation Theory

研討會訊息公告

主題
Tree Algorithm Seminar
主辦單位
演算法與計算理論學會
協辦單位
中華大學資訊工程系
時間
2016年11月15日(二)09:00~12:00
地點
中華大學創新廳(工程一館)
流程

9:00~9:50

Talk 1
Red-Black Trees
Speaker:靜宜大學資訊傳播系蔡英德教授
Abstract

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.


10:00~10:50

Talk 2
The VP and MVP Trees
Speaker:銘傳大學資訊工程系徐熊健教授
Abstract
Two elegant data structures: the vantage point tree (vp-tree) and multiple vantage point tree (mvp-tree) are introduced. Given a set X of n data points in a metric space, the vp-tree of X can be constructed in O(nlogn) by recursively choosing a vantage point randomly and performing the ball partition on the data point. Based on the vp-tree, whose height is O(logn), the range query problem, determining the points in X whose distances from the given point q are within the defined range, can be solved in O(logn) expected time. The mvp-tree adopts more than one vantage point and employs a larger size of data points in the leaf nodes to reduce the tree height as compared to the vp-tree. In addition, more efficient skills for bounding unnecessary branches could be developed in the mvp-tree so that the searching ability can be further improved.

11:00~11:50

Talk 3
The Top Trees
Speaker:中華大學資訊工程系梁秋國教授
Abstract

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 top-trees, can be used to provide an O(log n) time solution when facing these changes. Top trees are a dynamic self-adjusting 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 fully-dynamic 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.