DEV Community

Mohamed Allam
Mohamed Allam

Posted on • Originally published at mohamedallam.tech

Trees data structure with types (uses cases included)

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:

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)