Talk Abstract: A Tree is a hierarchical data structure that plays an essential role in several subareas of computer science. In this lecture, we will begin by talking about Binary Search Trees (BSTs) and analyze the circumstances in which searching can be efficiently done in logarithmic time or inefficiently done in linear time due to internal imbalance. Next, we will talk about the first known self-balancing binary search tree called AVL tree, which takes O(log n) time for inserting, searching, and deletion. Finally, we will use rotation techniques to ensure that a BST is always strictly balanced, thus taking O(log n) time for all basic operations.
Location: Sennott Square room 5317, 10:00-11:00 a.m. on Thursday, February 24th, 2022
Biosketch: Tiago Januario is a lecturer and researcher at the Department of Computer Science, Institute of Mathematics and Statistics, University of Bahia, Salvador, Brazil. He earned his Ph.D. in Computer Science from the University of Minas Gerais, with a focus on Combinatorial Optimization and Graph Theory. He was a Postdoc with the Computer Science Institute at the University of Paraíba, working the Scheduling and Vehicle Routing Problems. His interests include efficient data structures, graph theory, analysis of algorithms, local search, metaheuristics, combinatorial optimization, and logistics.
View this event on the School of Computing and Information events calendar.