Red Black Tree Red Black Tree Removal Case1: If removing a red node with no black child node , then we can remove this red node directly. Case2: If removing a black node with red child node, then change the color of that red child node. (Note: The above two cases are only for the removing node with one child node.) Case3: If removing a black node with two child nodes, replace with the in-order successor node and change color before removing the black node....
Regular Expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for “find” or “find and replace” operations on strings, or for input validation. Basic rule for Regex Quantifier(限定符):only for one character ?: means the character show up before ? once or zero, for example:...
Dot Language Dot language is a abstract grammar for defining Graphviz nodes, edges, graphs, subgraphs, and clusters. An edgeop is -> in directed graphs and -- in undirected graphs. Semicolons and commas aid readability but are not required. Also, any amount of whitespace may be inserted between terminals. Below is a example dot file: And it display the partial graph generated by the dot language:
Dijkstra’s Algorithm Given a weighted graph and a source vertex in the graph, find the shortest paths from the source to all the other vertices in the given graph. The process of the algorithm: 每次从未标记的节点中选择距离出发点最近的节点，标记并收录到最优路径集合中 计算刚加入节点A的邻近节点B的距离（不包含标记的节点），若节点A的距离+节点A到节点B的边长之和<节点B的距离，就更新节点B的距离和前面节点 循环直到目的地被标记 Node Starting Node Previous Node 0 0 1 4 0 2 12 1 3 19 2 4 21 5 5 11 6 6 9 7 7 8 0 8 14 2 From the table we know that the shortest path from node 0 to 4 is 21, we can also backtrace the path using the previous node from above: 4-5-6-7-0....
Minimum Spanning Tree A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Kruskal’s algorithm to find the minimum cost spanning tree uses the greedy approach....
Lambda Expressions One issue with anonymous classes is that if the implementation of your anonymous class is very simple, such as an interface that contains only one method, then the syntax of anonymous classes may seem unwieldy and unclear. In these cases, you’re usually trying to pass functionality as an argument to another method, such as what action should be taken when someone clicks a button. Lambda expressions enable you to do this, to treat functionality as method argument, or code as data....
Anonymous Classes in Java Anonymous classes enable you to make your code more concise. They enable you to declare and instantiate a class at the same time. They are like local classes except that they do not have a name. Use them if you need to use a local class only once. Anonymous classes can often used in graphical user interface (GUI) applications. Declaring Anonymous Classes public class HelloWorldAnonymousClasses { interface HelloWorld { public void greet(); public void greetSomeone(String someone); } public void sayHello() { class EnglishGreeting implements HelloWorld { String name = "world"; public void greet() { greetSomeone("world"); } public void greetSomeone(String someone) { name = someone; System....
CSV Formatted Data Comma-separated values (CSV) is a text file format that uses commas to separate values. A CSV file stores tabular data (numbers and text) in plain text, where each line of the file typically represents one data record. Each record consists of the same number of fields, and these are separated by commas in the CSV file. If the field delimiter itself may appear within a field, fields can be surrounded with quotation marks...
Btree The idea we saw earlier of putting multiple set (list, hash table) elements together into large chunks that exploit locality can also be applied to trees. Binary search trees are not good for locality because a given node of the binary tree probably occupies only a fraction of any cache line. B-trees are a way to get better locality by putting multiple elements into each tree node. Degree m: Maximum number of the children...
Makefile GNU Make is a tool which controls the generation of executables and other non-source files of a program from the program’s source files. Make gets its knowledge of how to build your program from a file called the makefile, which lists each of the non-source files and how to compute it from other files. When you write a program, you should write a makefile for it, so that it is possible to use Make to build and install the program....