3 Replies - 339 Views - Last Post: 19 November 2018 - 09:24 AM

#1 Triple IX   User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 13
  • Joined: 17-August 18

THEN WHY WE NEED A SPLAY TREE ....?

Posted 19 November 2018 - 01:10 AM

hello , friends .....

recently a question is came over my mind ..and i couldn't get any answer my self .....will you please help me about this ?

as we know a splay tree always rotate its children accordingly whenever any insertion is performed i.e. zig-zig,zag-zag,zig-zag,zag-zig . and main cause of this rotation is to keep its recently inserted child to place always in root node , so in this case insertion is very efficient.
and splay tree also not a height balanced tree. but its time complexity is o(log n), similar to all balanced tree. hence its called a balanced tree .

now , problem is that , if we insert our data like following in a binary search tree; then also we can get our recently inserted node at root place .... then why we need a splay tree ?? remember , splay tree not a height balanced tree ... i eagerly wait for your replies .. thanks


void insert_node(int x)
{
   node *temp = create_node(x);
   if (root==NULL)
    {root=temp;
     return;}
   if(root->data<x)
     {temp->left = root;
      root = temp;}
  else
   {temp->right = root;
      root = temp;}
}


This post has been edited by andrewsw: 19 November 2018 - 01:51 AM
Reason for edit:: removed ALL CAPS


Is This A Good Question/Topic? 0
  • +

Replies To: THEN WHY WE NEED A SPLAY TREE ....?

#2 andrewsw   User is offline

  • never lube your breaks
  • member icon

Reputation: 6818
  • View blog
  • Posts: 28,229
  • Joined: 12-December 12

Re: THEN WHY WE NEED A SPLAY TREE ....?

Posted 19 November 2018 - 01:53 AM

Please do not use ALL CAPS it is interpreted as shouting and is difficult (and annoying) to read.

Nor do you need bold, large, text.
Was This Post Helpful? 1
  • +
  • -

#3 Skydiver   User is online

  • Code herder
  • member icon

Reputation: 7056
  • View blog
  • Posts: 23,986
  • Joined: 05-May 12

Re: THEN WHY WE NEED A SPLAY TREE ....?

Posted 19 November 2018 - 08:03 AM

Although the code is in C, this question is more of a Computer Science question rather than a C question. Moving to Computer Science...
Was This Post Helpful? 0
  • +
  • -

#4 sepp2k   User is offline

  • D.I.C Lover
  • member icon

Reputation: 2754
  • View blog
  • Posts: 4,411
  • Joined: 21-June 11

Re: THEN WHY WE NEED A SPLAY TREE ....?

Posted 19 November 2018 - 09:24 AM

You've said it yourself: the operations on a splay tree are still O(log n) (well, ammortized O(log n) in the worst case). In your suggested tree, the find and delete operations will both be O(n) in the average case. And that's not just because it's extremely unbalanced (you never create a node with two children, so the height is always n), it's also not a search tree. Really it's just a funny-looking list.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1