11 docs tagged with "algorithms"

The goal of a B-tree is to not have to load an entire tree into memory. Only a bit by bit can be loaded in for processing. The order of a B-tree means something slightly different then with a normal tree.

A bag is a data structure that can contain the same element multiple times which is why it is often also called a multiset. The order of adding elements is not necessarily given, this depends on the implementation. Common operations on a bag are adding elements, removing elements and searching for a specific element.

A binary tree is a tree with the order of 2. Meaning that a node is either a leaf or has left and/or right child.

Trees have nodes that hold the data and edges which connect the nodes. An empty tree obviously has no nodes and therefore no data.

The goal of graph traversal is to visit each vertex in a graph. This can be done a multitude of ways.

Motivation

Priority queue

A set is a data structure that can hold unique elements. It represents a mathematical set which in german is called a "Menge". This means that an element is either in the set or it isn't. Just like with a bag you have the common operations of adding elements, removing elements and searching for a specific element.

Before we see how to find the shortest path from vertex $a$ to vertex $b$ we need to define a few things.

There are multiple ways of storing graphs. Depending on the type of graph and the requirements a certain storage method might be preferred.

The goal of a topological sort is given a list of items with dependencies, (ie. item 5 must be completed before item 3, etc.) to produce an ordering of the items that satisfies the given constraints. In order for the problem to be solvable, there can not be a cyclic set of constraints. (We can't have that item 5 must be completed before item 3, item 3 must be completed before item 7, and item 7 must be completed before item 5, since that would be an impossible set of constraints to satisfy.) Meaning we can model this problem with a directed unweighted acyclic graph. When all the vertices are topologically ordered in a row all the edges go from left to right.