Where and how are trees used in programming?

Question

Algorithms

Hey! I started studying algorithms and data structures and now I'm going through trees, but I can't find a clear definition of when and where they are used. Can you throw off useful articles or give examples? Thank you!

Answer 1

1. Something that actually has a tree form - for example, directory trees on disk, scene trees in 3D, decision trees.
2. Search trees are data structures that allow you to add or remove objects and allow you to quickly search by key. For example, all sorts of dictionaries, database indexes.
3. The so-called heap is a data structure that allows you to add or remove objects and maintains the minimum element in this set. It is used as an auxiliary in some algorithms.
4. Binary partitioning of space in 3D is a well-known way of sorting from far to near.
In addition, trees may not exist in memory, but only implied - in syntactic parsing, game-theoretic calculations. Although one of the options for intermediate storage of the parsed formula, so that later it can be used for multiple calculations, is a tree (but reverse Polish notation is more often used).

Answer 2

Trees are everywhere :)
The most banal example is a search tree, BST, balanced by BST (for example, red black tree, rb-tree), used to organize structures that store key-value pairs (for example, SortedMap - TreeMap implementation in Java).
Highly branched balanced trees (B-trees) are used to implement indexes in DBMS
Decision trees in machine learning are used to make decisions. Development of the idea - random forest, use of multiple decision trees.
Hash tree, or Merkle tree - in blockchains for storing transactions.
Prefix tree - for storing and searching key strings
Octrees, q-trees in games and graphics for dividing space into regions.
Even views in most GUI frameworks are organized as trees.
And I still haven't listed everything, 100%

Answer 3

By itself, a stupid tree is quite useless. But as a basic data organization, it is found in many places. If you hang some additional properties on it and support them, then you get cool stuff.
Balanced binary search trees are a very popular data structure. Used anywhere if you need to store a set or an associative array of something and change arbitrary elements.
Trees are also often used in string algorithms. There is such a structure - boron (trie) - allows you to efficiently store a bunch of strings and look for: is there such a string in the structure. More advanced algorithms like Aho-Korasika, Ukkonen also build a tree with additional chips and allow you to do cool things, such as search for a bunch of patterns in the text at once, or instantly find the most frequently occurring substring of a bottom size.
The heap is used for sorting and for implementing priority queues.
Further, trees in the sense of graphs are also used, for example, in the network. Routers build a spanning tree and issue commands along its edges.

Answer 4

In addition to what has already been said, there is also such a kind of trees as AST, which is used to describe the syntax. In almost all programming languages, templating is used to compile and interpret code. There is also a Nested Sets
algorithm for storing tree structures in the database, such as the category of something