UGC-NET DECEMBER 2015 ANSWER KEY PAPER 1

ANSWER KEY OF PAPER 1 – CBSE UGC NET EXAM 27 DECEMBER 2015 (UNOFFICIAL)

CBSE UGC NET December 2015 Answer Key – Unofficial.




UGC-NET DECEMBER 2015 COMPUTER SCIENCE ANSWER KEYS AND DESCRIPTIVE SOLUTION
http://cbsenetmaterial.blogspot.in/2015/12/ugc-net-december-2015-computer-science.html

NATIONAL ELIGIBILITY TEST (NET)

On behalf of UGC, the Central Board of Secondary Education announces holding of the National Eligibility Test (NET) on 27^th December, 2015 (SUNDAY) for determining the eligibility of Indian nationals for the Eligibility for Assistant Professor only or Junior Research Fellowship & Eligibility for Assistant Professor Both in Indian universities and colleges. CBSE will conduct NET in 83 subjects at 88 selected NET Examination Cities spread across the country.

The candidates who qualify for the award of Junior Research Fellowship are eligible to pursue research in the subject of their post-graduation or in a related subject and are also eligible for Assistant Professor. The universities, institutions, IITs and other national organizations may select the JRF awardees for whole time research work in accordance with the procedure prescribed by them. The award of JRF and Eligibility for Assistant Professor both OR Eligibility for Assistant Professor only will depend on the performance of the candidate in all three papers of NET. However, the candidates qualifying exclusively for Assistant Professor will not be considered for award of JRF.

---

Q1) Greater the handicap of the students
Answer: 3 (Teacher)

Q2) Characteristics of Continuous and Comrehensive Evaluation
Answer: 3 (b, c and d)

Q3) Which of the following attributes denote great
Answer: 4 (a, b, c and d)

Q4) which statement is correct in context of multiple choice questions
Answer: 4 (They are more subjective than true-false questions)

Q5) As chairman of an independent commission on education
Answer: 3 (Learning : the Treasure Within)

Q6) What are required for good teaching
Answer: 1 or 4 ()

Q7) Which of the following statements is not true in the context
Answer: 4 ()

Q8) Which of the following statements is true in the context of testing of a Hypothesis
Answer: 2 (It is only the null Hypothesis, that can be tested)

Q9) Which of the following are the basis rules of APA style
Answer: 2 (b, c and d)

Q10) Which of the following are the main characteristics of a seminar
Answer: 4 (a, b and d)

Q11) A researcher is interested in studying the prospects
Answer: 1 (Rating scale)

Q12) Ethical norms in research
Answer: 1 (Thesis Format)

Q13) When confronted with signing a big card
Answer: 1 (State of Confusion)

Q14) According to author, which one is not the most creative
Answer: 4 (Reading)

Q15) The entire existence of the author revolves round
Answer: 2 (a and b only)

Q16) How many teens, as per the Bic Survey, do not own a Pen
Answer: 4 (100)

Q17) What is the main concern of the Author
Answer: 4 (That the teens have forgotten the art of Handwriting)

Q18) The main objectives of student evaluation
Answer: 2 (b, c, and d only)

Q19) Using the central point of the classroom communication as the beginning
Answer: 1 (Systemization)

Q20) Aspects of the voice, other than the speech
Answer: 4 (Delivery Language)

Q21) Every type of communication is affected by its
Answer: 4 (Context)

Q22) Attitudes, actions and appearance in the context of classroom
Answer: 2 (Non verbal)

Q23) Most often, the teacher student communication is
Answer: 3 (Utilitarian)

Q24) In a classroom commuter’s trust level determined by
Answer: 4 (eye contact)

Q25) Next Term in the series 2,5,10,17, ….
Answer: 1 (50)

Q26) Group of 210 students appeared in tesr
Answer: 4 (72)

Q27) Anil after travelling 6 km towards east
Answer: 4 (10 km)

Q28) Next Term in the series B2E,….
Answer: 4 (J58Q)

Q29) A party was held
Answer: 2 (14)

Q30) P and Q are brothers
Answer: 3 (uncle)

Q31) Consider the argument given below, pre-employment testing of
Answer: 2 (Analogical)

Q32) Among the following propositions two are related in such a way
Answer: 4 (a and d)

Q33) a cluster of propositons with a structure 
Answer: 2 (An Argument)

Q34) Consider the following Assertion (A) and reason 
Answer: 1 (Both A and R are true but R does not)

Q35) A definition that has a meaning that is deliberately
Answer: 3 (Stipulative)

Q36) If the proposition ‘No men are Honest’ is taken to be false
Answer: 2 (Some men are honest)

Q37) which decade registered the..
Answer: 1 (1961-71)

Q38) Average decadal growth rate 
Answer: 2 (0.0982)

Q39) Based on the Average decadal growth rate 
Answer: 2 (38.49)

Q40) In 1951 power availability per person
Answer: 4 (500W)

Q41) In which decade the average power availability
Answer: 3 (2001-2011)

Q42) By what %age power increased from 1951 to 2011
Answer: 4 (9)

Q43) NMEICT stand for
Answer: 1 (National Mission on education Through ICT)

Q44) Instant Messaging application
Answer: 4 (a, b and c)

Q45) A byte consists of 
Answer: 2 (8 bits)

Q46) which is not input device
Answer: 4 (Monitor)

Q47) Open source software
Answer: 3 (Mozila Firefox)

Q48) Same letter to different persons in MS word
Answer: 4 (Mail Merge)

Q49) Inside Rural homes, the source/sources of Nitrogen Oxide Pollution
Answer: 4 (a, b and c)

Q50) Which of the following pollutants
Answer: 3 (Lead)

Q51) Assertion A : People population
Answer: 1 (Both A and R are true and R is correct)

Q52) which is not natural Hazards
Answer: 4 (Chemical Contamination)

Q53) National climate change policy
Answer: 4 (350 GW)

Q54) per capita energy consumption
Answer: 3 (Russia, China, Brazil, India)

Q55) Rashtriya Uchattar Shiksha Abhiyan
Answer: 2 (a, b and c)

Q56) The grounds of which discrimination in admission
Answer: 2 (a, b and c)

Q57) Which of the following are correct about Lok Sabha
Answer: 1 (a and c)

Q58) Public order in constitutuion
Answer: 2 (The State List)

Q59) The term of office of the advocate General
Answer: 4 (Not Fixed)

Q60) Highest no of seats in Lok Sabha
Answer: 1 (Maharashtra)

UGC-NET DECEMBER 2015 COMPUTER SCIENCE ANSWER KEYS AND DESCRIPTIVE SOLUTION

Answer keys and descriptive solution of UGC-NET Computer Science held on December 28, 2015 is available on 

www.brainstormachiever.com

or

Click Here

Corrections and Suggestions are Welcomed

UGC-NET DECEMBER 2015 ANSWER KEY PAPER 1

http://cbsenetmaterial.blogspot.in/2015/12/ugc-net-december-2015-answer-key-paper-1.html

ugc-net december 2015,ugc-net december 2015 answer key,ugc-net computer science december 2015 answer keys,ugc-net computer science december 2015 complete solution,cbse net december 2015,cbse net december 2015 answer key,cbse net computer science december 2015 answer keys,ugc-net computer science december 2015 complete solution

UGC-NET COMPUTER SCIENCE PAPER-3 SEPTEMBER 2013 WITH ANSWER KEY

UGC-NET COMPUTER SCIENCE PAPER-3 SEPTEMBER 2013 WITH ANSWER KEY

ugc net computer science question papers,ugc net computer science december 2014 question papers,
ugc net computer science june 2014 question papers,
ugc net computer science december 2014 question papers,
ugc net computer science june 2013 question papers,
ugc net computer science december 2013 question papers,
ugc net computer science june 2012 question papers,
ugc net computer science december 2012 question papers,
ugc net computer science june 2011 question papers,
ugc net computer science december 2011 question papers,
ugc net computer science june 2010 question papers,
ugc net computer science december 2010 question papers,
ugc net computer science june 2009 question papers,
ugc net computer science december 2009 question papers,
ugc net computer science june 2008 question papers,
ugc net computer science december 2008 question papers,

ugc net computer science previous question papers, ugc net computer science previous year question papers, ugc net previous question papers, ugc net old question papers, 

UGC-NET COMPUTER SCIENCE PAPER-2 SEPTEMBER 2013 WITH ANSWER KEY

UGC-NET COMPUTER SCIENCE PAPER-2 SEPTEMBER 2013 WITH ANSWER KEY

UGC-NET Computer Science Neural Networks, Artificial Intelligence, Fuzzy Logic and Predicate Logic Previous Year Questions

UGC-NET Computer Science Study Material Theory of Computation

Theory of Computation Lecture by Dr. Ankush Mittal Ex-Associate Professor (IIT Roorkee)

UGC-NET December 2015 Admit Card

Click Here to Download Admit Card for UGC-NET December 2015

UGC-NET Computer Science Study Material Compiler Book by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman

UGC-NET Computer Science Compiler Book by Alfred V. Aho, Ravi Sethi, Jeffrey D. Ullman

Click Here to Download pdf

UGC-NET Computer Science Study Material Computer Graphics Schaum Series

UGC-NET Computer Science Computer Graphics Schaum Series

Click Here to Download pdf

UGC-NET Computer Science Study Material Compiler Design Handwritten Notes

UGC-NET Computer Science Compiler Design Handwritten Notes

Click Here to Download

UGC-NET COMPUTER SCIENCE OPERATING SYSTEM QUESTIONS WITH EXPLANATION

In this Blog we are providing all the UGC-NET Computer Science previous year Questions with explanation:

Q :  For the implementation of a paging scheme, suppose the average process size be x bytes,

the page size be y bytes, and each page entry requires z bytes. The optimum page size that

minimizes the total overhead due to the page table and the internal fragmentation loss is

given by

(A) x/2

(B) xz/2

(C) √(2xz)

(D) √(xz)/2

(UGC-NET Computer Science December 2014 )

Answer: (C)

Explanation:

Important consideration is size of pages to use. OS often has choice in this matter---many MMUs allow various different page sizes.

• Small size: less wasted space due to internal fragmentation; fewer unused pages in memory.
• Large page size: more efficient disk I/O, smaller page tables

If average process segment size is x; page table entry size is z bytes; page size is y,

Average amount of internal fragmentation per segment is y/2.

Average number of pages per process segment is x/y. Each page requires 'z' bytes of page table, so each process segment requires page table size of xz/y bytes.

Total overhead per segment, therefore, due to internal fragmentation and page table entries, is

xz/y + y/2

To minimize the overhead, differentiate with respect to page size, y, and equate to 0:

-xz/y² + 1/2 = 0
=> y = √(2xz)

So for example, if the average segment size were 256 K, and the page table entry size were 8 bytes, the optimum page size, to minimize overhead due to page table entries and internal fragmentation, would be √(2 × 256K × 8) = 2048 = 2K.

Note: that this calculation ignores the need to keep page sizes large in order to speed up paging operations; it only considers memory overheads.


ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers
ugc net computer science december 2008 question papers

UGC-NET COMPUTER SCIENCE COMPUTER GRAPHICS and DATA & IMAGE PROCESSING Previous Year Questions

UGC-NET COMPUTER SCIENCE COMPUTER GRAPHICS and DATA & IMAGE PROCESSING Previous Year Questions

UGC-NET COMPUTER SCIENCE COMPUTER GRAPHICS and DATA & IMAGE PROCESSING Previous Year Questions
ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers
ugc net computer science december 2008 question papers

UGC-NET COMPUTER SCIENCE COMPUTER NETWORKS Previous Year Questions

UGC-NET COMPUTER SCIENCE COMPUTER NETWORKS Previous Year Questions

UGC-NET COMPUTER SCIENCE COMPUTER NETWORKS Previous Year Questions
ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers
ugc net computer science december 2008 question papers

UGC-NET COMPUTER SCIENCE Operating System Previous Year Questions

UGC-NET COMPUTER SCIENCE Operating System Previous Year Questions

UGC-NET COMPUTER SCIENCE Operating System Previous Year Questions
ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers

ugc net computer science december 2008 question papers

UGC-NET COMPUTER SCIENCE DBMS Previous Year Questions

UGC-NET COMPUTER SCIENCE DBMS Previous Year Questions

UGC-NET COMPUTER SCIENCE DBMS Previous Year Questions
ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers

ugc net computer science december 2008 question papers

UGC-NET COMPUTER SCIENCE Software Engineering Previous Year Questions

UGC-NET COMPUTER SCIENCE Software Engineering Previous Year Questions

UGC-NET COMPUTER SCIENCE Software Engineering Previous Year Questions

ugc net computer science question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2014 question papers
ugc net computer science december 2014 question papers
ugc net computer science june 2013 question papers
ugc net computer science december 2013 question papers
ugc net computer science june 2012 question papers
ugc net computer science december 2012 question papers
ugc net computer science june 2011 question papers
ugc net computer science december 2011 question papers
ugc net computer science june 2010 question papers
ugc net computer science december 2010 question papers
ugc net computer science june 2009 question papers
ugc net computer science december 2009 question papers
ugc net computer science june 2008 question papers

ugc net computer science december 2008 question papers

Java final Keyword

final keyword in Java

There are three uses of final keyword in Java :

1. To declare named constants
2. To prevent a class from being inherited
3. To prevent a method from overriding 

We will discuss here all these one by one.

Declaring constants:

A variable can be declared as final. Doing so prevents its contents from being modified. This means that you must initialize a final variable when it is declared.

(In this usage, final is similar to const in C/C++/C#.) For example:

final int FILE_NEW = 1;

final int FILE_OPEN = 2;

final int FILE_SAVE = 3;

final int FILE_SAVEAS = 4;

final int FILE_QUIT = 5;

Variables declared as final does not occupy memory on per-instance basis.

Preventing inheritance:

Sometimes you will want to prevent a class from being inherited. To do this, precede the class declaration with final. Declaring a class as final implicitly declares all of its methods as final, too. As you might expect, it is illegal to declare a class as both abstract and final since an abstract class is incomplete by itself and relies upon its subclasses to provide complete implementations.

Here is an example of a final class:

final class A

{

// ...

}

// The following class is illegal.

class B extends A

{ 

// ERROR! Can't subclass A

// ...

}

As the comments imply, it is illegal for B to inherit A since A is declared as final.

Preventing Overriding: 

While method overriding is one of Java’s most powerful features, there will be times when you will want to prevent it from occurring. To disallow a method from being overridden, specify final as a modifier at the start of its declaration. Methods declared as final cannot be overridden. The following fragment illustrates final:

class A 

{

          final void meth()

         {

                   System.out.println("This is a final method.");

          }

}

class B extends A

{

          void meth()

          {

               // ERROR! Can't override

          }

}

Note:

Also if a method in Java if declared as final it is telling the compiler to make its definition inline as its definition will not be changed by the subclasses. 

UGC-NET Computer Science JAVA Questions with Explanation

Q : 1 Which method is called first by an applet program ?

(A) start( )

(B) run( )
(C) init( )

(D) begin( )

(UGC-NET December 2014 Paper 3)

Answer: (C) init()

Explanation:

Applet Life Cycle

When an applet begins, the AWT calls the following methods, in this sequence:
1. init( )
2. start( )
3. paint( )

When an applet is terminated, the following sequence of method calls takes place:
1. stop( )
2. destroy( )

1. init( )

The init( ) method is the first method to be called. This is where you should initialize variables. This method is called only once during the run time of your applet.

2. start( )

The start( ) method is called after init( ). It is also called to restart an applet after it has been stopped. Whereas init( ) is called once—the first time an applet is loaded—start( ) is called each time an applet’s HTML document is displayed onscreen. So, if a user leaves a web page and comes back, the applet resumes execution at start( ).

3. paint( )

The paint( ) method is called each time your applet’s output must be redrawn. This situation can occur for several reasons. For example, the window in which the applet is running may be overwritten by another window and then uncovered. Or the applet window may be minimized and then restored. paint( ) is also called when the applet begins execution. Whatever the cause, whenever the applet must redraw its output, paint( ) is called. The paint( ) method has one parameter of type Graphics. This parameter will contain the graphics context, which describes the graphics environment in which the applet is running. This context is used whenever output to the applet is required.

4. stop( )

The stop( ) method is called when a web browser leaves the HTML document containing the applet—when it goes to another page, for example. When stop( ) is called, the applet is probably running. You should use stop( ) to suspend threads that don’t need to run when the applet is not visible. You can restart them when start( ) is called if the user returns to the page.

5. destroy( )

The destroy( ) method is called when the environment determines that your applet needs to be removed completely from memory. At this point, you should free up any resources the applet may be using. The stop( ) method is always called before destroy( ).

In some situations, your applet may need to override another method defined by the AWT, called update( ). This method is called when your applet has requested that a portion of its window be redrawn. The default version of update( ) first fills an applet with the default background color and then calls paint( ). If you fill the background using a different color in paint( ), the user will experience a flash of the default background each time update( ) is called—that is, whenever the window is repainted. One way to avoid this problem is to override the update( ) method so that it performs all necessary display activities. Then have paint( ) simply call update( ).

Interrupts in Computer Architecture

Interrupts:

An interrupt is a signal to the processor emitted by hardware or software indicating an event that needs immediate attention. An interrupt alerts the processor to a high-priority condition requiring the interruption of the current code the processor is executing. The processor responds by suspending its current activities, saving its state, and executing a function called an interrupt handler (or an interrupt service routine, ISR) to deal with the event. This interruption is temporary, and, after the interrupt handler finishes, the processor resumes normal activities. There are two types of interrupts: hardware interrupts and software interrupts.

Hardware and Software Interrupts:

Hardware interrupts are used by devices to communicate that they require attention from the operating system. Internally, hardware interrupts are implemented using electronic alerting signals that are sent to the processor from an external device, which is either a part of the computer itself, such as a disk controller, or an external peripheral. For example, pressing a key on the keyboard or moving the mouse triggers hardware interrupts that cause the processor to read the keystroke or mouse position. Unlike the software type (described below), hardware interrupts are asynchronous and can occur in the middle of instruction execution, requiring additional care in programming. The act of initiating a hardware interrupt is referred to as an interrupt request (IRQ).

A Software Interrupt is caused either by an exceptional condition in the processor itself, or a special instruction in the instruction set which causes an interrupt when it is executed. The former is often called a trap or exception and is used for errors or events occurring during program execution that are exceptional enough that they cannot be handled within the program itself. For example, if the processor's arithmetic logic unit is commanded to divide a number by zero, this impossible demand will cause a divide-by-zero exception, perhaps causing the computer to abandon the calculation or display an error message. Software interrupt instructions function similarly to subroutine calls and are used for a variety of purposes, such as to request services from low-level system software such as device drivers. For example, computers often use software interrupt instructions to communicate with the disk controller to request data be read or written to the disk.

Each interrupt has its own interrupt handler. The number of hardware interrupts is limited by the number of interrupt request (IRQ) lines to the processor, but there may be hundreds of different software interrupts. Interrupts are a commonly used technique for computer multitasking, especially in real-time computing. Such a system is said to be interrupt-driven.

Internal and External Interrupts:

An Internal Interrupt is a specific type of interrupt that is caused by instructions embedded in the execution instructions of a program or process. Typically, internal interrupts resist changes by users, and happen "naturally" or "automatically" as a processor works through program instructions, rather than being caused by external events or network connections.

An External Interrupt is a computer system interrupt that happens as a result of outside interference, whether that’s from the user, from peripherals, from other hardware devices or through a network. These are different than internal interrupts that happen automatically as the machine reads through program instructions.

UGC-NET Computer Science Splay Tree

Splay Tree

A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time(amortized analysis is a method for analyzing a given algorithm's time complexity). For many sequences of non-random operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown. The splay tree was invented by Daniel Dominic Sleator and Robert Endre Tarjan in 1985.

All normal operations on a binary search tree are combined with one basic operation, called splaying. Splaying the tree for a certain element rearranges the tree so that the element is placed at the root of the tree. One way to do this is to first perform a standard binary tree search for the element in question, and then use tree rotations in a specific fashion to bring the element to the top. Alternatively, a top-down algorithm can combine the search and the tree reorganization into a single phase.

Operations to be performed on Splay Tree:

Splaying:

When a node 'x' is accessed, a splay operation is performed on 'x' to move it to the root. To perform a splay operation we carry out a sequence of splay steps, each of which moves 'x' closer to the root. By performing a splay operation on the node of interest after every access, the recently accessed nodes are kept near the root and the tree remains roughly balanced, so that we achieve the desired amortized time bounds.
Each particular step depends on three factors:

• Whether x is the left or right child of its parent node, p,
• whether p is the root or not, and if not
• whether p is the left or right child of its parent, g (the grandparent of x).

It is important to remember to set 'gg' (the great-grandparent of 'x') to now point to 'x' after any splay operation. If 'gg' is null, then 'x' obviously is now the root and must be updated as such.

There are three types of splay steps, each of which has a left- and right-handed case. For the sake of brevity, only one of these two is shown for each type.

These three types are:

1. Zig step:

This step is done when p is the root. The tree is rotated on the edge between x and p. Zig steps exist to deal with the parity issue and will be done only as the last step in a splay operation and only when x has odd depth at the beginning of the operation.

2. Zig-zig step:

This step is done when p is not the root and x and p are either both right children or are both left children. The picture below shows the case where x and p are both left children. The tree is rotated on the edge joining p with its parent g, then rotated on the edge joining x with p. Note that zig-zig steps are the only thing that differentiate splay trees from the rotate to root method introduced by Allen and Munro prior to the introduction of splay trees.

Join:

Given two trees S and T such that all elements of S are smaller than the elements of T, the following steps can be used to join them to a single tree:

• Splay the largest item in S. Now this item is in the root of S and has a null right child.
• Set the right child of the new root to T.

Split:

Given a tree and an element x, return two new trees: one containing all elements less than or equal to x and the other containing all elements greater than x. This can be done in the following way:

• Splay x. Now it is in the root so the tree to its left contains all elements smaller than x and the tree to its right contains all element larger than x.
• Split the right subtree from the rest of the tree.

Insertion:

To insert a value x into a splay tree:

• Insert x as with a normal binary search tree.
• Splay the newly inserted node x to the top of the tree.

Alternative Method:

• Use the split operation to split the tree at the value of x to two sub-trees: S and T.
• Create a new tree in which x is the root, S is its left sub-tree and T its right sub-tree.

Deletion

To delete a node x, use the same method as with a binary search tree: if x has two children, swap its value with that of either the rightmost node of its left sub tree (its in-order predecessor) or the leftmost node of its right subtree (its in-order successor). Then remove that node instead. In this way, deletion is reduced to the problem of removing a node with 0 or 1 children. Unlike a binary search tree, in a splay tree after deletion, we splay the parent of the removed node to the top of the tree.

Alternative Method:

• The node to be deleted is first splayed, i.e. brought to the root of the tree and then deleted. leaves the tree with two sub trees.
• The two sub-trees are then joined using a "join" operation.

Search:

The search operation in Splay tree does the standard BST search, in addition to search, it also splays (move a node to the root). If the search is successful, then the node that is found is splayed and becomes the new root. Else the last node accessed prior to reaching the NULL is splayed and becomes the new root.

There are following cases for the node being accessed:

1)When  Node is root We simply return the root, don’t do anything else as the accessed node is already root.

2) Zig: When Node is child of root (the node has no grandparent). Node is either a left child of root (we do a right rotation) or node is a right child of its parent (we do a left rotation).
T1, T2 and T3 are subtrees of the tree rooted with y (on left side) or x (on right side)

                y                                     x
               / \     Zig (Right Rotation)          /  \
              x   T3   – - – - – - – - - ->         T1   y 
             / \       < - - - - - - - - -              / \
            T1  T2     Zag (Left Rotation)            T2   T3

3) When Node has both parent and grandparent.There can be following subcases:

•  Zig-Zig and Zag-Zag:

Node is left child of parent and parent is also left child of grand parent (Two right rotations) OR node is right child of its parent and parent is also right child of grand parent (Two Left Rotations).

Zig-Zig (Left Left Case):
       G                        P                           X       
      / \                     /   \                        / \      
     P  T4   rightRotate(G)  X     G     rightRotate(P)  T1   P     
    / \      ============>  / \   / \    ============>       / \    
   X  T3                   T1 T2 T3 T4                      T2  G
  / \                                                          / \ 
 T1 T2                                                        T3  T4 

Zag-Zag (Right Right Case):
  G                          P                           X       
 /  \                      /   \                        / \      
T1   P     leftRotate(G)  G     X     leftRotate(P)    P   T4
    / \    ============> / \   / \    ============>   / \   
   T2   X               T1 T2 T3 T4                  G   T3
       / \                                          / \ 
      T3 T4                                        T1  T2

•  Zig-Zag and Zag-Zig:

Node is left child of parent and parent is right child of grand parent (Left Rotation followed by right rotation) OR node is right child of its parent and parent is left child of grand parent (Right Rotation followed by left rotation).Zig-Zag (Left Right Case):

       G                        G                            X       
      / \                     /   \                        /   \      
     P   T4  leftRotate(P)   X     T4    rightRotate(G)   P     G     
   /  \      ============>  / \          ============>   / \   /  \    
  T1   X                   P  T3                       T1  T2 T3  T4 
      / \                 / \                                       
    T2  T3              T1   T2                                     

Zag-Zig (Right Left Case):
  G                          G                           X       
 /  \                      /  \                        /   \      
T1   P    rightRotate(P)  T1   X     leftRotate(P)    G     P
    / \   =============>      / \    ============>   / \   / \   
   X  T4                    T2   P                 T1  T2 T3  T4
  / \                           / \                
 T2  T3                        T3  T4  

Example:

 
         100                      100                       [20]
         /  \                    /   \                        \ 
       50   200                50    200                      50
      /          search(20)    /          search(20)         /  \  
     40          ======>     [20]         ========>         30   100
    /            1. Zig-Zig    \          2. Zig-Zig         \     \
   30               at 40       30            at 100         40    200  
  /                               \     
[20]                              40

The important thing to note is, the search or splay operation not only brings the searched key to root, but also balances the BST. For example in above case, height of BST is reduced by 1.

Advantages

Good performance for a splay tree depends on the fact that it is self-optimizing, in that frequently accessed nodes will move nearer to the root where they can be accessed more quickly. The worst-case height—though unlikely—is O(n), with the average being O(log n). Having frequently used nodes near the root is an advantage for many practical applications (also see Locality of reference), and is particularly useful for implementing caches and garbage collection algorithms.

Advantages include:

• Comparable performance—average-case performance is as efficient as other trees.
• Small memory footprint—splay trees do not need to store any bookkeeping data.
• Possibility of creating a persistent data structure version of splay trees—which allows access to both the previous and new versions after an update. This can be useful in functional programming, and requires amortized O(log n) space per update.
• Working well with nodes containing identical keys—contrary to other types of self-balancing trees. Even with identical keys, performance remains amortized O(log n). All tree operations preserve the order of the identical nodes within the tree, which is a property similar to stable sorting algorithms. A carefully designed find operation can return the leftmost or rightmost node of a given key.

Disadvantages

The most significant disadvantage of splay trees is that the height of a splay tree can be linear. For example, this will be the case after accessing all n elements in non-decreasing order. Since the height of a tree corresponds to the worst-case access time, this means that the actual cost of an operation can be high. However the amortized access cost of this worst case is logarithmic, O(log n). Also, the expected access cost can be reduced to O(log n) by using a randomized variant.

The representation of splay trees can change even when they are accessed in a 'read-only' manner (i.e. by find operations). This complicates the use of such splay trees in a multi-threaded environment. Specifically, extra management is needed if multiple threads are allowed to perform find operations concurrently. This also makes them unsuitable for general use in purely functional programming, although they can be used in limited ways to implement priority queues even there.

Summary

• Splay trees have excellent locality properties. Frequently accessed items are easy to find. Infrequent items are out of way.
• All splay tree operations take O(Log(n)) time on average. Splay trees can be rigorously shown to run in O(log n) average time per operation, over any sequence of operations (assuming we start from an empty tree)
• Splay trees are simpler compared to AVL and Red-Black Trees as no extra field is required in every tree node.
• Unlike AVL tree, a splay tree can change even with read-only operations like search.