List implemented using an inorder binary tree

Question

For the new computer science assignment we are to implement a list/array using an inorder binary tree. I would just like a suggestion rather than a solution.

The idea is having a binary tree that has its nodes accessible via indexes, e.g.

t = ListTree()
t.insert(2,0) # 1st argument is the value, 2nd the index to insert at
t.get(0) # returns 2

The Node class that the values are stored in is not modifiable but has a property size which contains the total number of children below, along with left, right and value that point to children and store the value accordingly.

My chief problem at the moment keeping track of the index - as we're not allowed to store the index of the node in the node itself I must rely on traversing to track it. As I always start with the left node when traversing I haven't yet thought of a way to recursively figure out what index we are currently at.

Any suggestions would be welcome.

Thanks!

Answer 1

You really wouldn't want to store it on the node itself, because then the index would have to be updated on inserts for all nodes with index less than insert index. I think the real question is how to do an in-order traversal. Try having your recursive function return the number of nodes to its left.

Answer 2

Well, a node in a binary tree cannot have a value and an index. They can have multiple pieces of data but the tree can only be keyed/built on one.

Maybe your assignment wants you to use the index value as the key to the tree and attach the value to the node for quick retrieval of the value given an index.

Answer 3

Does the tree have to be balanced? Does the algorithm need to be efficient?

If not, then the simplest thing to do is make a tree in which all the left children are null, i.e., a tree that devolves to a linked list.

To insert, recursively look go to the right child, and then update the size of the node on the way back out. Something like (pseudocode)

function insert(node, value, index, depth)
    if depth < index
        create the rightchild if necessary
        insert( rightchild, value, index, depth + 1)
    if depth == size
        node.value = value
    node.size = rightchild.size + 1

After you have this working, you can modify it to be more balanced. When increasing the length of the list, add nodes to the left or right child nodes depending on which currently has the least, and update the size on the way out of the recursion.

To generalize to be more efficient, you need to work on the index in terms of its binary representation.

For example, and empty list has one node, without children with value null and size 0.

Say you want to insert "hello" at index 1034. Then you want to end up with a tree whose root has two children, with sizes 1024 and 10. The left child has no actual children, but the right node has a right child of its own of size 2. (The left of size 8 is implied.) That node in turn, has one right child of size 0, with the value "hello". (This list has a 1-based index, but a 0-based index is similar.)

So you need to recursively break down the index into its binary parts, and add nodes as necessary. When searching the list, you need to take care when traversing a node with null children

Answer 4

I don't think you want to store the index, rather just the size of each subtree. For insance, if you wanted to look up the 10th element in the list, and the left and right subrees had 7 elements each, you would know that the root is the eight element (since it's in-order binary), and the first element of the right subree is 9th. armed with this knowledge, you would recurse into the right subree, looking for the 2nd element.

HTH

Answer 5

how did you figure out indexing in the end?

Answer 6

A very easy solution is to do GetFirst() to get the first node of the tree (this is simply finding the leftmost node of the tree). If your index N is 0, return the first node. Otherwise, call GetNodeNext() N times to get the appropriate node. This isn't super efficient though since accessing a node by index takes O(N Lg N) time.

Node *Tree::GetFirstNode()
{
    Node *pN,*child;
    pN=GetRootNode();
    while(NOTNIL(child=GetNodeLeft(pN)))
    {
     pN=child;
    }
    return(pN);
}


Node *Tree::GetNodeNext(Node *pNode)
{
    Node *temp;

    temp=GetNodeRight(pNode);
    if(NOTNIL(temp))
    {
     pNode=temp;
     temp=GetNodeLeft(pNode);
     while(NOTNIL(temp))
     {
      pNode=temp;
      temp=GetNodeLeft(pNode);
     }
     return(pNode);
    }
    else
    {
     temp=GetNodeParent(pNode);
     while( (NOTNIL(temp)) && (GetNodeRight(temp)==pNode) )
     {
      pNode=temp;
      temp=GetNodeParent(pNode);
     }
     return(temp);
    }
}