Whats a tree
A tree is a collection of nodes, each node holds some data, one of the nodes is the root node, and other nodes. are disjoints subsets and each subset is a tree or a sub tree.
Each node has exactly one parent, and can have one or more children, no single node has more than one parent.
Trees are everywhere:
- If you wrote any switch statement but didnt knew why its more efficient than a bunch of if-else statements, the answer is Look up tables (LUT) which may use BST
- Operating systems use trees for File system.
- The syntactic representation of a programming language is Abstract syntax tree. AST
- Browser Document object model (DOM)
- Databases use Log structured merge tree. LSM tree
- SQL index use b-tree.
- Dynamic memory management uses heap. which is a type of a tree.
- A trie for dictionaries or auto complete algorithms.
- Priority queues as well use heap.
- Garbage collectors also use trees.
https://en.wikipedia.org/wiki/Tree_(graph_theory)
https://en.wikipedia.org/wiki/Tree_(data_structure)
Nodes or vertices
Nodes is every unit of data
Edges or paths (links)
Its the connection between each two nodes, if we have N nodes we would have N-1 edges, because each node as parent, except the root node.
Root
Is the upmost node, who has no parent, and have only children, for the children nodes this is their most parent node, generally in the top of the tree.
Parent-Children
A node is a parent to its very next descendants. the descendants are the children to whom its connected with one single edge.
Siblings
Are the children connected to the same node.
Descendants
When we want to talk about children and their children, and the children of their children..etc we would say descendants.
It means the set of nodes we can reach from a particular node going to its children. so all the subtree.
Ansestors
From that node to the root node, all this nodes are considered anscestors.
Degree of nodes
Is the number of children a node has, so the direct children.
A degree of a tree cannot be told from a tree, but its predefined, we can say its a binary tree. but if its unbalanced, we would see it in a form of a linkedlist.
Leaf nodes, external or terminal
All nodes who has no children. so with nodes with degree 0
Levels
Levels starting from first level 1, the root, as we categorize each level by all the nodes who take the same number of edges to get to the root node.
Height
Hight of nodes, is the same as the levels but it starts from 0, its very useful for analysis.
Forest
A collection of a tree is called a forest. which at least has a root node.
To convert a forest to a tree, we attach the roots of the present trees, to one single root.
Types of trees
There is many types of trees, and they are extremely useful and popular. for example
Binary tree
One of the most popular trees, is the binary tree,
Its tree of degree 2, means every node can have 0,1 or 2 children, but not more than 2.
deg(T)=2
$children={{0,1,2}}$
- Because the nodes can have only 2 nodes, we call them left child and right child. or left node and right node.
- If we come across a tree that is unbalanced, means it forms something like a linked list, but to the left side, we call it left skewed binary tree. or right skewed binary tree
Binary search tree
The binary search tree or BST , is a derivate of binary tree, but with a constraint in the data, Its a rooted binary tree, where every node (data) on the left side is grater than nodes on the right side.
$deg(T)=2$
AVL Tree
Another tree named after inventors Adelson-Velsky and Landis, is a self balancing binary search tree.
Decision Tree
Its one of the popular ones for classification and prediction.
Fenwich Tree
A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.
Link to wiki
Log structured Merge Tree
Or LSM tree one of the trees used in databases like influxDB.
Top comments (0)