Union-Find is a data structure that mimics tree data structure except that nodes point to their parent instead of children. The union-find is very useful for set operations such as the following.1. find – find the root of the current node2. same component – check if two trees have the same root node. (belongs to the same set)3. union (merge) – merge two trees (sets) into one Such operations are very useful for problems like connected components – each node belongs to only one connected component – and vertex coloring. The union-find is useful for algorithms such as minimum-spanning tree READ MORE
Tag: data structure
Intro to Array data structure Part 2 – 2D Array
Continuing from the last post I am going to discuss more about the array data structure which is 2D array.In this post, I will focus on the basic concept and usage. What is 2D Array? 2D array is basically array within array.Typically array contains specified data type in its element.However, it is possible that the element can contain another array instead! This is a 2D array with 3 rows and 5 columns.In each row, there is an array of size 5 which is the column size.In other words, there is an array of size 3 (row) and there is another READ MORE
Intro to Array data structure Part 1
Today, we will go over a popular data structure – array.This is the most basic and fundamental data structure in computer science regardless of any programming language.Even many complex data structures use array inside the implementation.Programming language like python doesn’t have array but it provides list instead. (of course, python list is much more flexible and easier to use than C++ array)In this post, I will go over some important characteristics of array with example code based on C++. What is Array? Array is a contiguous piece of memory of a certain data type.It sounds hard but it will be READ MORE
Intro to Linked List data structure
Today, we will go over a popular data structure – linked list.Linked list may not make much sense for some languages such as python and javascript since there is already a good one such as list. However, since linked list is quite useful for languages like C++ it is still worthwhile to go over.In this post I will go over some important characteristics about linked list and strengths and weaknesses.Please note that all the explanations will be based on C++. What is Linked List? Linked list is a data structure that each node is connected like a chain via pointer.It READ MORE