Grade 11 · 8 algorithmsCitește în română

TreesArbori

Every trees algorithm from the Romanian high school curriculum, with the idea explained, its complexity, examples and code you can edit and run right here.

Create a free account Browse the collection

8algorithms
7chapters
1grade

Trees

Arbori · 8 algorithms

Minimum spanning tree (Kruskal's algorithm)Arborele parțial de cost minim (algoritmul lui Kruskal)Kruskal builds the minimum spanning tree starting from n trees with a single node each. We sort the edges by cost in increasing order (on ties they…O(n²)
Minimum spanning tree (Prim's algorithm)Arborele parțial de cost minim (algoritmul lui Prim)In a connected undirected graph with edge costs we look for a spanning tree (n - 1 edges connecting all nodes) with the minimum total cost. Prim…O(n²)
Binary search tree: insert, search, sorted printArbore binar de căutare: inserare, căutare, afișare sortatăIn a binary search tree, for every node, all values in the left subtree are smaller than the node's value and those in the right subtree are larger.…O(n)
Children, descendants and ancestors of a nodeFiii, descendenții și ascendenții unui nodThe tree is given by its parent array (t[root] = 0). The children of x are the nodes i with t[i] = x. A node y is a descendant of x if, climbing…O(n²)
Diameter of a treeDiametrul unui arboreThe diameter of a tree is the length (number of edges) of the longest path between two nodes. The two-traversal method: we run a BFS from node 1 and…O(n)
Traversals of a binary treeParcurgerile unui arbore binarIn a binary tree every node has at most two children: a left one and a right one. We store it with the arrays st[i] and dr[i] (0 if the child is…O(n)
Parent array: root, leaves, levels, heightVectorul de tați: rădăcină, frunze, niveluri, înălțimeA rooted tree can be stored as a parent array: t[i] is the parent of node i, and for the root t[i] = 0. The root is the node with t = 0. The leaves…O(n²)
Checking whether a graph is a treeVerificarea că un graf este arboreA tree is a connected undirected graph without cycles. For a graph with n nodes the following statements are equivalent: it is a tree; it is…O(n²)