Trees


Trees are widely used data structure. In this chapter we will try to unveil some of the key terms related to key, organization of a tree, and how a tree can be made. Let’s see the general structure of a tree

In the above tree, we can see that the Node “P” is the top most node and it is called “Root”

Q ,R and S are linked to P and they are called the children of P.

P is the parent. Q ,R and S are known as siblings.

T,U and V are the children of Q and, they are siblings.

If you observe above, we have not restricted the number of the children that a node can have.(there are some special type of trees, where the number of children is limited.)

What is a tree node?

The tree can be defined as a collection of nodes in a particular fashion. So what is a node?

A node is a data object which consists of some “actual” data and some pointers for connecting this node with the other nodes so that the structure of the tree is formed. See below a typical node.

some terminology:

Height of a Node:



How to start?

This blog is structured in the below way:

Click on the menu for each topic, you will find three categories

1. Theory

2. Capsules

3. Questions

1. Theory:

Detailed chapter wise theory with links to GATE previous year questions related to the theory. I recommend everyone read this and then approach the GATE questions, as it adds to you knowledge.

2. Capsules:

There are snippets of theory, which is important with respect to the previous year GATE questions.

As the name suggests, these are for quick study and if you find it difficult to understand, please go back to the detailed theory link mentioned. I RECOMMEND THIS ONLY FOR QUICK RECAP.

3. Questions:

Solved question papers of previous year’s GATE exams. Definitely give it a try.

THIS IS WHAT GOING TO MATTER IN SCORING.

Basics of Operating System

Lets start with a broad view of a computing system there are 4 major components of a computing system:

  1. Hardware – CPU, Memory, I/O devices
  2. Operating System
  3. Application Programs – Compilers, web browsers, text editor programs
  4. Users

“What is an Operating System(OS)?”

OS itself is a piece of software, which runs all the time. We can say OS is similar to a government. It provides an environment in which the application programs can run. It creates this environment by performing different functions. Let’s see what the main functions of operating systems are.

As we discussed earlier, a computing system has hardware, and users. The operating system acts as middle man between these two by providing some services to both hardware and user.

From the user perspective, below are the functions of OS.

  • User Interface:There are Command Line Interface (CLI) and Graphical User Interface(GUI) provided by OS, through which the users can interact with hardware like I/O devices, memory space
  • I/O Operations: OS regulates the use of I/O devices by the user. For protection and efficiency usually user cannot directly interact with the I/O device. OS provide a means to do I/O operations. For example OS controls multiple users using a single printer.
  • File system manipulation: users may need to create and delete files, write to files and search for files. Operating system keeps track of all these file related activities. For example, if a user writes something to a file using a text editor application, OS keeps track of this write, so that the modification on the file reflects on the storage device.
  • Communication: certain times, user programs would need to communicate with each other. OS provides a means to inter-process communication via message passing and shared memory(we will see these two in detail later)
  • Error detection: there may be several error in CPU memory hardware(like power failure), in I/O devices and user programs. OS gracefully handles the error conditions so that the hardware and data is not damaged by the error.

The above 5 functions are OS functions provided to the user. Lets see what are the functions that OS provides to the computing system so that efficiency of the system is achieved. The below functions are important in multi-user and multi processing scenarios.

  • Resource allocation: There are several resources in a computer like CPU time, memory space, file storage space, I/O devices. Application programs requests these resources. There would be numerous user programs running at the same time, hence OS makes a decision on what to allocate to which user program. OS takes the decision in such a way that maximum efficiency is achieved.

    • Protection:There may be scenarios where multiple processes run at the same time. What will happen if a process can interfere with other, or it can interfere with the OS itself (remember, OS is also a program) there may be some malicious process, intentionally trying to harm the system too. OS provides protection to the system by limiting access to the system resources

    • Security: Security of the system from the outsiders(meaning those who are not indented to use this system)is also provided by OS. Each user have an account and they must provide a password to access their account. This is very important in a multi-user environment.

    So, we have seen the what an OS is and what are the main functions of the Operation System. Next chapter we will see the notion of “process” and how CPU is shared between multiple processes. We will also see an important topic of process scheduling.

    Operating System Theory

    1. Basics of Operating System - what is OS? What are the functions?