rodrigosobral2000/assignments_2020_aed

A brief approach data structures, including AVL and RB trees. As well as sorting algorithms, including Merge and Radix sort.

Algorithms and Data Structures Assignments

---

Used Technologies 💻

---

Data Structures - AVL and RB Trees 🌳

About 📋

AVL Trees

Are a type of binary search tree in which the heights of the two child subtrees of any node differ by at most one. Otherwise it self-balances.

When a new node is inserted into an AVL tree, it is first inserted into a regular binary search tree. Then the tree is rotated to restore the AVL property.

Search, insert and delete operations take O(log n) time in both the average and worst cases.

See more 📚

RB Trees

Are a type of binary search tree in which all the nodes are either red or black.

When a new node is inserted into a RB tree, it is first inserted into a regular binary search tree. Then the tree is rotated to restore the RB property.

Search, insert and delete operations take O(log n) time in both the average and worst cases.

See more 📚

Sorting Algorithms - Key Comparasion & Manipulations Based 🔑

Key Comparasion Based - Merge Sort

Is a divide and conquer algorithm that sorts a list of elements by recursively splitting the list into two equal halves, sorting each half, and then merging the two sorted halves. The merge step is the most difficult step of the algorithm.

Time complexity of merge sort is O(n log n) in all cases.

Key Manipulation Based - Radix Sort

Is a sorting algorithm that sorts data based on the digits in the number. It works by dividing the input list into a number of lists, each containing only numbers that have a certain digit in the position being considered. Then the lists are merged to produce the final sorted output. That's why it is a non-comparative sort algorithm. In this case, the first digit being considered is the least significant digit.

Time complexity of radix sort is O(nk) where k is the number of digits in the largest number in the input list.

---

Contributors ✨

Licenciatura Engenharia Informática - Universidade de Coimbra
Algoritmos e Estruturas de Dados - 2019/2020
Coimbra, 17 de abril de 2020

🎓 Rodrigo Sobral

---

License 🔗

Have a look at the license file for details

---