The AVL tree, named after its inventors Georgy Adelson-Velsky and Evgenii Landis, is a type of self-balancing binary search tree. The tree re-organises itself after every insert and delete so that the tree height is approximately \log n nodes high, allowing search in O(\log n) time. The re-organising does not guarantee a perfectly balanced tree, it is however good enough to guarantee O(\log n) search.
Here is a collection of my favourite articles I've written. I hope you enjoy them and learn something!
The splay tree is a type of self-adjusting binary search tree like the red-black tree. What makes the splay tree special is its ability to access recently accessed elements faster. Whenever an operation is performed, the tree performs an operation called splaying which pulls the element to the top of the tree.
A Fibonacci heap is a heap data structure similar to the binomial heap, only with a few modifications and a looser structure. The Fibonacci heap was designed in order to improve Dijkstra’s shortest path algorithm from O(m \log n) to O(m + n \log n) by optimising the operations used most by the algorithm. Its name derives from the fact that the Fibonacci sequence is used in the complexity analysis of its operations.
A binomial heap is a priority queue data structure similar to the binary heap only with a more strict structure, it supports quicker merging of two heaps in Θ(\log n) at the cost of a slower find minimum operation. A binomial heap is made up of a series of unique ‘binomial trees’ which are constructed from smaller binomial trees.
A binary heap is a binary tree data structure that typically uses an array or list as its underlying data structure. Heaps are one of the fundamental data structures that all software developers should have in their toolkit due to its fast extraction of either the minimum or the maximum element in a collection.
A binary search tree (BST) is a node-based tree data structure in which each node can have at most two children, it supports several operations common to any search tree such as search, insert and delete.
Visual Studio Code version 1.17 is getting a new rendering engine based on HTML canvas. This post dives into some of the motivation and how it was done.
Hot exit comes to Visual Studio Code in version 1.8.0.
Bucket sort, also known as bin sort, is a distribution sort that works by arranging elements into several ‘buckets’ which are then sorted using another sort, typically insertion sort, and merged into a sorted list.
This article dives deep into the colours, formatting and customisation of gnome-terminal, the default bash terminal for Ubuntu. The majority of this article applies to many terminal variants, not only to Gnome/Ubuntu.
Counting sort is a distribution sort that achieves linear time complexity given some trade-offs and provided some requirements are met.
East-Asian languages are a bit of a mess on the internet for a number of reasons, such as browser implementation, the presence of system fonts and web developers neglecting to address the issue on their side. This article dives deep into how languages work on the web and the problems that can occur.
Git is a source control (or version control) system designed and developed by Linus Torvalds back in 2005 for the development of the Linux kernel. Similar to other source control systems like TFS or Subversion, it manages your source code enabling a team to work on the same project while minimising conflicts.
There is a lot to cover when making a website. So much that it’s unreasonable to manually check a site for best practices in SEO, performance, accessibility, style and so on. Luckily the internet has you covered with these great tools to push your site to the next level!
Here are some of the commands I find useful for Android’s
adb. They can be used manually or to automate your build or testing process.
Design patterns in software engineering are generic solutions to some commonly occurring problems encountered when creating software. They are incredibly useful tools for both communicating a solution to a problem to other developers and also for saving time solving problems that have already been solved in quite elegant ways. Learning the big design patterns is a also just a great way to improve your skills as a software developer.
Creating triangles with CSS is a pretty good way to reduce the number of images within an application. They’re a bit tricky to get your head around at first but once you understand them it’s really easy.
I’ve compiled some information about time complexity and underlying data structures of .NET simple collections and dictionaries. It was difficult to find some of this information on official sources like MSDN and non-official sources seemed to differ, so I used reflector and actually had a look at the .NET framework code to confirm these cases.
Display and editor templates in ASP.NET MVC let us create views in a more maintainable and elegant ways. This article looks at how to define custom templates to display and manipulate different data types.
Quicksort is an O(n^2) sorting algorithm that runs in O(n \log n) time on average. It has a number of favourable qualities; it’s an in-place sort, requiring O(\log n) auxiliary space in the worst case; and is also a divide and conquer algorithm making it easy to parallelise. Unfortunately however it’s not a stable sort.
Insertion sort works by looking at each item in an array (starting with the second) and comparing it with the item before. If the item before is larger, they are swapped. This continues until the item is smaller at which point we do the same for the next item.
Merge sort is a sorting algorithm that runs in O(n \log n) time. It is a divide and conquer algorithm, so it can get the most out of today’s multi-cored systems. It works by continually splitting up the array until each item stands on its own. The items are then merged back with the items that they were split with in the correct order.
Game development introduced me to programming when I was around 10 years old, and I’ve loved it ever since. One of the first formal algorithms I learned before entering university was A* (pronounced “A star”), and I really had a great time learning about it. It’s one of the most widely used pathfinding algorithms and is one that you would likely be introduced to first when approaching the subject of pathfinding. A pathfinding algorithm takes a start point (also known as a node) and a goal and attempts to make the shortest path between the two given possible obstacles blocking the way.
LSD radix sort is a stable distribution sort similar to bucket sort, that distributes values into buckets based on the digits within the value.