1

Representation 1 - Multi walk tree

typedef struct multiWalkTreeNode{
  struct multiWalkTreeNode * parent;
  void *item;
  struct multiWalkTreeNode **childPointer;
}Node;

typedef struct multiWalkTree{
  Node *root;
  int size; /*Number of nodes in the tree*/
}Tree;

Pictorial view:

enter image description here

Representation 2 - LCRS tree

typedef struct SiblingTreeNode{
  struct SiblingTreeNode *parent;
  void *item;
  struct SiblingTreeNode *firstChild;
  struct SiblingTreeNode *nextSibling;
}Node;

typedef struct LCRSTree{
  Node *root;
  int size;
}Tree;

Pictorial view:

enter image description here

Representation 3 - Tree using list(How to name this tree?)

typedef struct DListNode{
  int item;
  struct DListNode *next;
  struct DListNode *prev;
}DListNode;

typedef struct DList{ //Circular
  DListNode *head;
  int size;
}List;


typedef struct treeNode{
  struct treeNode *parent;
  void * item;
  List *childList;
  /* Sentinel node is created on initial construction of a "List" */
}Node;

typedef struct treeUsingList{
  Node *root;
  int size;
}Tree;

Pictorial view: enter image description here


Parent pointer is introduced to perform DFS without recursion or explicit stack.

Please confirm the correctness of representation.

Question:

1) Do we have any name for tree in Representation 3?

2) For insert/delete/find operations, which representation performs better?

3) Are there any other representations for rooted tree, that can enhance performance?

8
  • Where did you get this code from? Can you tell us if you know that this data structure actually has a well-known name and you just don't know what it is, or that you have no idea if it's even a well-known data structure? Dec 12, 2016 at 23:06
  • @RobertHarvey From no where. I wrote it. What are you trying to verify? Dec 12, 2016 at 23:08
  • Is it your own design? Dec 12, 2016 at 23:09
  • @RobertHarvey I don't know, what design mean? in just representing the data structure? Are you talking about Representation 3? My teacher in cs 61B hinted that, one can use list instead of sibling nodes. So, I wrote corrsponding code but I do not know the name of Representation 3. Dec 12, 2016 at 23:11
  • What makes you think it has a well-known name? If you and your teacher designed and wrote it, why would we know more about it than you? Dec 12, 2016 at 23:12

2 Answers 2

3

Here are some considerations:

  1. In #1, you aren't capturing a size of the childPointer array, so you cannot know how many children there are.

  2. Your code for #3 uses void *item in the text, but Node *item in the diagram. Further, the items labeled sentinel have (struckthru) item, next and prev, but should (to match the text) have head and size .

  3. None of these data structures are optimized for find operations, so among these, the fewer data structures the better, within a small margin (as none is great for find). If find is the primary concern I'd move to a totally different data structure (e.g. B-Tree or balanced binary tree, or anything else)!

  4. The #3 choice, I see as basically broken. It uses a doubly linked list, which at first blush might imply some improvement for large numbers of children regarding insert/delete. However, observe that the parent pointers from the nodes only refer to other tree nodes, and not also to the position in the doubly linked list (which themselves do not offer a parent pointer). So a full traversal of immediate children is still necessary, just like in option #2, and, the doubly linked list offers no improvement, just more maintenance required and space taken (all bad).

  5. Workload is going to be the primary concern here regarding which is best for performance. Regular trees (not one of your options) would be the best for insertion if there are, say, two or fewer children. For huge numbers of children, a doubly linked list might be better, but not if implemented as #3.

7
  • For your point #4 and #5, In representation #3, Are you saying that parent in treeNode should point to DListNode? Can you elaborate on that? Dec 13, 2016 at 20:41
  • #3 is using a doubly linked list but not taking any advantage of it relative to a singly linked list. Try writing the delete operation, for example, for #2 and for #3 (as it is), it will come out almost the same, with a search from the start for the node in the list. The advantage of the doubly linked list is not having to search backward for immediate predecessor. But if you're searching from the start anyway, you know the immediate predecessor, so doubly linked is no additional help over singly linked. (An alteration to #3 would be able to eliminate the search-for-node-from-start.)
    – Erik Eidt
    Dec 13, 2016 at 20:44
  • *1) did not get this point *parent pointers from the nodes only refer to other tree nodes, and not also to the position in the doubly linked list My understanding is, parent pointers of treeNode should point to other treeNode. *2) I did not get this point *For huge numbers of children, a doubly linked list might be better, but not if implemented as #3. Dec 13, 2016 at 20:48
  • What that means is you cannot reach the doubly linked list elements given the tree node without a search of the parent's child linked list nodes.
    – Erik Eidt
    Dec 13, 2016 at 20:51
  • In rep#3, How would you reach child treeNode's without traversing linked list? Dec 13, 2016 at 20:55
0

You can regard the representation 3 as a binary tree which is just arranged differently. So instead of going down you order the element on the same level. You can also call it a graph, since you have back-pointers.

Generally a hash can improve things tremendously. Since you did not state for what purpose you want better performance it's hard to give any statement.

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.