Add splay tree

[czgdp1807]

Description of the problem

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/Splay_tree
.. [2] https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects

[ka1shi]

I would like to work on it. Please assign it to me.

[czgdp1807]

Hi @ka1shi If you are participating through RGSoC, 2020 then feel free to start your work on this in a PR. However, if you are a GSSoC participant the see this list of issues. Feel free to open new issues if you have new ideas to work upon.

[ka1shi]

Hi @czgdp1807, I am participating through GSSoc20. Sure, I will check the issues with GSSoc20 tag. Thank You!

[Vanshika266]

Hi, Can I start working on this issue as a part of RGSoC20?

[czgdp1807]

Hi @Vanshika266 Please start by coming up with an API design for splay tree. You can take a look at https://en.wikipedia.org/wiki/Splay_tree#Operations for some ideas.Let us know if you face any problem/query.

[Vanshika266]

Thank you for allowing me to work on this issue.

I believe the class design would extend binary search tree implementation from pydatastructs. The basic structure of class can be as follows-
class SplayTree(BinarySearchTree): represents splay trees.

Following are the function APIs which can be implemented in the class -

• def _splay(self,x):
  Splay operation is performed on x i.e. node x is moved to the root, if x is present in the splay tree.
  x - The node last accessed in the splay tree
  According the position of node x in the splay tree, one of the following operations can be called inside operation splay -
  • def _zig(self,x):
    operation _zig is called when the last accessed node x is the left child or right child of the root.
  • def _zig_zig(self,x):
    operation _zig_zig is called when parent p of node x is not the root and either both p and x are left children or both right children of the root.
  • def _zig_zag(self,x):
    operation _zig_zag is called when parent p of node x is not the root and p is a left child and node x is a right child of the root or vice versa.
• def insert(self,key,data):
  The data is inserted using BinarySearchTree function insert and then the inserted node x is splayed using _splay.
• def delete(self,x):
  Node x is first searched using inherited search function which gives parent p of node x. Node x is then deleted using inherited delete function and node p is splayed.
• def join(self,key,root):
  It joins the self tree and the other tree whose root is passed as parameter.
  If all elements of the self tree are smaller than all elements of the other tree, then largest element of self tree is splayed and root of the other tree is inserted as right child of the self tree.
• def split(self,key,x):
split returns two trees, one having nodes with value less than x and other with nodes having value more than x. Node x is splayed, then right sub tree of x is split from the complete tree returning the two required trees.

References - https://en.wikipedia.org/wiki/Splay_tree

Kindly check if these APIs work.

[czgdp1807]

The public API looks good. Aren't the rotations(_zig_zig, etc.) same as those in AVLTree?

[Vanshika266]

Yes, I get your point. I will extend AVL Tree implementation from pydatastructs. Updated structure of the class can be -
class SplayTree(AVLTree): represents splay trees
I will override the insert and delete functions in Splay Tree implementation. I will call the implementation of AVLTree rotations(_left_rotate, etc.) inside rotation functions(_zig_zag, etc.) of SplayTree to maintain the consistency of splay tree nomenclature (_zig_zag, etc).

Kindly check if these updates work.

[czgdp1807]

Sounds better. Probably, it's time to make a PR.

[Vanshika266]

Ok, I will try to create a PR in a day or two for splay tree implementation.

[Vanshika266]

I have created a PR. I have implemented all the APIs except join and split. In join function, I need to merge two arrays of trees into one tree array and in split function, I need to divide one array into two tree arrays. So, should I make changes in the given tree arrays or create new ones?

Also, In case of join, If I merge two arrays then the complexity of join function would increase from O(log(n)) to O(m) [ n: number of elements in tree1, m: number of elements in other tree ]. Similarly for split function. So should I switch from array implementation to pointer implementation or leave these APIs, what do you suggest?

Also can you review the code once to see if it is the required implementation?

[czgdp1807]

It looks we don't need these two join and split in other methods like, insert, search and delete. So, IMO their complexities shouldn't matter much.

[Vanshika266]

Ok, I will add the implementation of join and split methods. Also, In join method, should I create new array for joined tree or extend the array of tree1 to append elements of the other tree ?

[czgdp1807]

Also, In join method, should I create new array for joined tree or extend the array of tree1 to append elements of the other tree ?

IMO, extending self.tree will be better according to the API of join. It is a method of the object, so it should change the object.

[Vanshika266]

I have extended self.tree in join method. Also, I have added the implementation of join and split methods in SplayTree.
Can you review the code once to see if it is the required implementation?