2

I have implemented a Splay Tree class that uses nodes to store data. In this class I have tried to convert the data of nodes into a Singly Linked List. 1,000,000 nodes can be inserted into the splay tree and it works perfectly. Using recursion I get a StackOverFlow error when the tree contains 1,000,000 nodes. However when the tree contains around 15000 nodes it is able to be converted to a linked list without a problem.

Here is the code for my toList Method that is inside the splay tree class

public LinkedList<Node> toList() {

   LinkedList<Node> list = new LinkedList<Node>();
   Node node = root;
   addToList(node, list);

   return list;
}

private void addToList(Node node, LinkedList<Node> list) {
   if(node != null) {
      addToList(node.left, list);
      list.add(node);
      addToList(node.right, list);
   }
}

I used this test class below to test the function of this method

@Test
public void testConversionToLinkedList {
   SplayTree<Integer,String> st = new SplayTree<Integer,String>();
   for(int i = 0; i < 1000000; i++) {
      st.insert(i, Integer.toString(i));
   }
   assertEquals(1000000, st.size());

   LinkedList<Node> list = st.toList();
   assertEquals(1000000, list.size());
}

The test passes when the size entered is around 15000, however any number greater than that will show a StackOverFlowError

The error occurs at the line addToList(node.left, list);

This is really weird because when i used the same recursion technique to print the data of the nodes into a txt file, there is no StackOverFlow error and the data prints perfectly.

I have tried to use In Order Traversal, PreOrder and PostOrder but I still receive the same error at 1,000,000 nodes. I do know that it could be doing recursion too deeply and the stack runs out of memory. If that is the case is there any way I can convert a splay tree of nodes into a linked list? Any idea what could be going wrong? cheers

Yanzal
  • 113
  • 1
  • 8

3 Answers3

0

Your poblem is the recursive algorithm. As you figured out there is a limit in the stack size, which is build when you have recursion.

You can always transform recursion to a loop.

here are some examples for DFS and BFS algorithms using loops: Non recursive Depth first search algorithm

Sorontur
  • 500
  • 4
  • 15
  • You can always transform recursion to a loop but must often also use a stack. Since the stack overflow here is a problem, a naive translation of a recursive algorithm into a stack based loop may also run into memory problems. The root issue is that splay trees can become arbitrarily unbalanced. – MattArmstrong Oct 06 '22 at 10:05
0

You can increase the stack’s size. To do it you have to pass parameter to the jvm. The format is -Xss[g|G|m|M|k|K]. For example: java -Xss4m YourTreeProgram

niemar
  • 612
  • 1
  • 7
  • 16
0

The root issue is that splay trees can have a height equal to their node count, so the recursive algorithms you often see applied to binary trees are risky when applied to splay trees.

The easiest approach is to splay the tree as you go.

  1. Find the tree's minimum node. Simply follow the "left" links from the root all the way until they are null. Splay this node to the root, then add it to your list.
  2. Find its successor. I.e. follow the root's "right" link once, then follow "left" repeatedly until null. Splay that node to the root, then add it to your list.
  3. Repeat step 2 until there is no successor (i.e. the root's "right" link is null).

Finding the minimum and successor nodes are no different from other kinds of trees.

MattArmstrong
  • 349
  • 3
  • 9