Trees in Computer Science?!?!

Learn about the tree which is a key root of knowledge in Computer Science!

0
153
BSTfeaturedimage

In computer science, there are many ways to organize data to be used effectively. These many ways are called Data Structures. Of the many data structures, there are data structures that are hierarchical in which the data is organized into a tree-like structure. A specific tree data structure that will be taught is a Binary Search Tree.

In order to learn draw a Binary Search Tree, one must be able to learn the basic things that will help understand.

A binary search tree is similar to a family tree in a way. Before we begin, lets learn about the different terms that will be useful in understanding.

Node – a single place where data is.

Children – the data linked and below another piece of data

Root – the highest point of data

Leaf – the data at the ends

The nodes, root, leaf nodes, and children in a BST

 

Now that you know the basics, lets learn specific topics that help understand the different forms of a tree.

 

Full –every node

other than the leaves has two children

Complete – every level, except possibly the last, is completely filled, and all nodes are as far left as possible

Height- the longest path from the root node to a leaf node

Depth – number of edges from the specific node from the root node

These are different forms of a tree.
This shows the height and depth of a tree

 

A binary search tree is a binary tree in which the nodes have a value that is greater than all values in its left subtree and smaller than all values in its right subtree.

This is how a BST looks like

 

In order to insert to a BST, you start from the root of the tree and check if the value is greater than or less than that value and if it is greater than the value, then you go to the right and check again if it is greater than or less than the value and so on and so forth until you get to the end where you add that value to the tree.

This is how to insert data into a BST

 

Deleting a node in BST

When deleting a node within a BST, there are many considerations to check for. The first thing to check is to see if the specific node has any children.

  • If the node has 0 children
    • In this case, you simply delete the node from the BST
  • If the node has 1 child
    • In this case, you replace the node to delete with the child
  • If the node has 2 children
    • In this case, you must replace the node with either the predecessor or successor
      • A predecessor is the maximum value in the node’s left subtree
      • A successor is the minimum value in the node’s right subtree
Deleting from BST, if the node to delete has 0 children.
Deleting from BST, if the node to delete has 1 child.
Deleting from BST, if the node to delete has 2 children.

 

Good job! You have now mastered one fundamental aspect within Computer Science and are one step closer to being a programming genius!!!

 

Citations:

Binary Trees. (2009). Retrieved from https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/trees.html