Welcome to Computer Science 101
In these posts, we will cover important and famous concepts from the world of computer science.
Today's Topic: Binary Search Trees
I have to admit - back in the days of my studies (Sergey here btw.), I was kind of a nerd. Well, maybe still am, but not in a bad way ;)
Coming fresh from high school I already knew a lot about computer science. Yet for some weird reasons, I used to struggle with binary search trees a lot during my first term.
Not because it was a hard concept to grasp - but because, as many people, it took me time getting used to more abstract concepts in computer science.
As most of you probably know: Trees in computer science, are not a huge plant that magically grows out of your hard-drive, instead of soil.
In fact - all the trees in computer science are pretty weird in general. For example, they all have their root on the very top and grow top-down. WTF??
Yeah I know - computer science can be weird at times. It's like studying maths, physics, and sometimes even botany at the same time :)
Anyways - let's start our journey to understanding CS better, with a little expedition on a very simple kind of tree: A binary search tree (BST)
So first of all - what is a tree?
In computer science, a tree is an abstract data structure. That means that it's just a way to access data and doesn't really say anything about how the data is stored physically.
Any tree consists of so-called nodes and edges. Nodes are the parts that store some data. Edges are connections (references/pointers) between certain nodes. For trees, we call them "branches".
What makes a tree now a tree (and not just an arbitrary graph - you'll learn about them in another post), is that the existence of very top node, we call a "root". From this root, you can only go downwards to the nodes of the next layer.
This is how you can imagine it graphically:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Here the node "8" is the root node. "/" and "\" are the branches.
Binary Trees
A binary tree is a special type of tree, where every node can have at most two branches to lower-nodes.
The example you've seen before is a binary tree.
So now what is a binary search tree then?
A binary search tree is a special type of binary tree where the nodes are organized in a particular way to make searching for values efficient. Each node has a value, and for every node:
- All values in the left subtree are less than the node's value.
- All values in the right subtree are greater than the node's value.
And why do we need binary search trees?
Binary search trees allow algorithmically efficient and quick finding, inserting, or deleting values in a sorted collection of data.
So basically, it makes it easier for a computer to search through this thing and add or remove new information.
For example, consider searching a word in a dictionary, with alphabetical order vs. searching a word in just a random pile of text.
So why do we tell you about this?
You see - binary search trees are one of the fundamental concepts in the first terms of computer science studies. Therefore, we understood that a true computer science apparel shop needs at least one design related to them.
Trees can be theoretical and boring - but drawn onto paper, they can be intruguing, colorful and artistic.
So if you want to wear that amazing data structure on your newest hoodie, check out The_Adventurer now!