Definition

The Tree

A Tree is an abstract data type that is composed of Nodes where each Node can contain 0 or more child Nodes. Moreover, unlike an array, linked lists, stacks, and queues, Trees are not a linear data structure therefore a Tree can be empty with no nodes or the root node and zero or more subtrees.

The must known types of Trees

Binary Search Tree

A binary search tree or BST is so effective in searching, and that's because it gives a specific order to all the nodes. In a BST the left node is always smaller than its parent and the right one is greater.

The Node in BST

When talking about Trees you need to make sure to understand what is Node, like I point out in the diagram, each Node has 3 parts: a value, a reference to a left node if it exists, and a reference to a right node if it exists. So each node has its own value and 2 links to children that can be null in case I don't have one.

Binary tree

Simply a Binary tree is a tree where each node has 0, 1, or 2 children nodes. We can distingue 2 types: balanced or unbalanced binary tree. You always would prefer to use balanced binary trees cause they are more performant than unbalanced. With a balanced tree, access is O(log n). With an unbalanced tree, access is O(n) (worst case).

Application of a Binary Search Tree

• Graphics:

Game engines for example use it in 3d rendering to determine which object to render.

• Compilers:

Compilers use a syntax tree which is a type of BST to parse syntax expression.

• Search Applications.

Performance

------------Average---------- | -----------Worst-----------

• Insert --> Θ(log(n)) ==> fast / -->O(n) ==> slow
• Delete --> Θ(log(n))==> fast / -->O(n) ==> slow
• Search --> Θ(log(n)) ==> fast / -->O(n) ==> slow
• look up --> Θ(log(n)) ==> fast / -->O(n) ==> slow

Conclusion

BST can be more powerful and performant but this data structure also has a weak point. BST can get unbalanced which would reduce its performance a lot. However, engineers had created a variety of solutions like the AVL Trees and the Red-Black Trees which can transform an unbalanced tree into a balanced one.

if you want to find more info, this resource would help u a lot.

AVL Tree animation:

https://www.cs.usfca.edu/~galles/visualization/AVLtree.html

Red-Black Trees animation:

https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Binary Heaps

Definition

A BH is a Binary Tree with Two additional features:

• it's a complete binary tree(all levels are filled).

• each value is >= if it's a max-binary heap or <= if it's a min-binary heap as I explain in the diagram.

Performance

------------Average---------- | -----------Worst-----------

• Insert --> Θ(1) ==> fast / -->O(log(n)) ==> slow
• Search --> Θ(n) ==> fast / -->O(n) ==> slow
• look up --> Θ(n) ==> fast / -->O(n) ==> slow

Conclusion

Heaps has a bad performance at searching and even look as u may notice, well that's because they aren't made for that purpose, heaps are so good when you want to compare data or insert or operating on the min value if it's min-BH or the max-value if it's a max-BH and that's way it's a common way to implement priority queues.

Priority Queue

Priority Queue is a type of queue where each element have a priority and it's served based on that priority. And we need to mention that we can set priorities according to our needs. So for example if you want the biggest number to have the most priority or maybe the smallest or any other need. The best way for you to get this perfectly is to try out this cool animation: https://visualgo.net/en/heap

Trie

(Photo from Wikipedia) Trie is also called a prefix tree, it's a specialized tree in searching where the values inside its nodes are usually letters and it usually outperforms other data structures such as arrays, hash tables, or BST. Trie has a lot of applications such as Full-text search, autocompletion, searching of préfix, and more.