Original Post
🔒 Locked
Representing a tree
Advertisement
Quote:
Original post by Motorherp
You could simply use stl vectors, so you might start out with something like:template <class T> class TreeNode{ T m_data; int m_parentIndex; std::vector<int> m_childrenIndicies;}template <class T>class Tree{ std::vector< TreeNode<T> > m_nodes;}
Thank you for the suggestion. But this kind of tree is hard to traverse, isn't it? For instance, if I want to go from Node A to the next sibling of the parent of Node A, I'll have to find the iterator of the parent of Node A, which takes O(n).
Edit: On second thought, I was wrong. Please forget what I've said.
Quote:
Original post by snooty Quote:
Original post by Motorherp
You could simply use stl vectors, so you might start out with something like:template <class T> class TreeNode{ T m_data; int m_parentIndex; std::vector<int> m_childrenIndicies;}template <class T>class Tree{ std::vector< TreeNode<T> > m_nodes;}
Thank you for the suggestion. But this kind of tree is hard to traverse, isn't it? For instance, if I want to go from Node A to the next sibling of the parent of Node A, I'll have to find the iterator of the parent of Node A, which takes O(n).
The idea of tree structures is to recurse up and down rather than across. If you're having to traverse across the tree very often then maybe you should consider using a different container for your data other than a tree. There are ways around this however. For example, if during tree creation you create all a nodes children before moving onto its grandchildren or siblings children you end up with all siblings next to each other in the vector. This way you can jump to siblings by simply taking the next node in the vector to the one you're currently on. In fact if you do it this way there's not even any need to store a vector of children indicies in each node, you can simply store the offset to the first child and the number of children present instead. Of course this will only work for static trees however.
Another way, one that allows you to avoid having a variable-size container in each node, and instead have a fixed size node structure, is to treat a binary tree slightly different way. To do so, treat the left child node of a node as the first proper child of that node. Treat the right child node of a node as the next sibling of that node, rather than as a child. This results basically as having a singly-linked list for the list of childs that each parent has.
What appears as this in binary tree format:
Would instead be interpretted as this:
Another way to just shift around the lines in the binary tree format to show how this really works would be to make the left branches (which indicate children) vertical, and the right branches (which indicate siblings) horzontal:
Granted, this will only work well in situations where you don't need to address each child by index, but that's very frequently the case anyway.
What appears as this in binary tree format:
Root / A / \ B C / \ / \ D E F G Would instead be interpretted as this:
Root / | \ / | \ / | \ A C G / \ / B E F / D Another way to just shift around the lines in the binary tree format to show how this really works would be to make the left branches (which indicate children) vertical, and the right branches (which indicate siblings) horzontal:
Root / A-------C---G / / B---E F / D Granted, this will only work well in situations where you don't need to address each child by index, but that's very frequently the case anyway.
Quote:
Original post by Motorherp
The idea of tree structures is to recurse up and down rather than across. If you're having to traverse across the tree very often then maybe you should consider using a different container for your data other than a tree. There are ways around this however. For example, if during tree creation you create all a nodes children before moving onto its grandchildren or siblings children you end up with all siblings next to each other in the vector. This way you can jump to siblings by simply taking the next node in the vector to the one you're currently on. In fact if you do it this way there's not even any need to store a vector of children indicies in each node, you can simply store the offset to the first child and the number of children present instead. Of course this will only work for static trees however.
This method is nice for creating static trees. But insertion and deletion would be expensive (It is the problem of vector actually).
Since I may be choosing the wrong data structure, I'll explain what I want to do.
I'm trying to implement a data structure that resemble the win32 list view control (That's why I chose a tree for obvious reasons). Traversal of the data (if it is a tree) would require going from Node A to the next sibling of the parent of Node A (from A to 3).
root
--Node 1
--Node 2
----Node X
----Node Y
----Node A
--Node 3
What would be a good data structure for it?
Any suggestions appreciated.
Edit: I mean tree view control.
Quote:
Original post by snooty Quote:
Original post by ToohrVyk
type 'a tree = Node of 'a * (tree list)
I'm sorry, but this is kinda hard to understand. Could you explain please?
This line of code is the definition of an O'Caml union type. It states that a tree is in fact a node (the root) which contains an object (of type 'a) and a list of children (which are, in turn, the roots of their own subtrees). O'Caml is a language originally designed to write compilers in general, and manipulate syntax and decorated syntax trees in particular. Its tree definition and traversal capabilities are far greater than those of C-family languages.
In C++, this could be translated as:
template<typename A> struct tree { A data; std::list<tree<A> > children;};This approach supports recursively defined operations on the tree quite well.
Quote:
Original post by snooty
Since I may be choosing the wrong data structure, I'll explain what I want to do.
I'm trying to implement a data structure that resemble the win32 list view control (That's why I chose a tree for obvious reasons). Traversal of the data (if it is a tree) would require going from Node A to the next sibling of the parent of Node A (from A to 3).
root
--Node 1
--Node 2
----Node X
----Node Y
----Node A
--Node 3
What would be a good data structure for it?
Any suggestions appreciated.
Actually the binary tree I had above might do this very well. To do an entirely iterative rather than recursive traversal, you could start at the root node. Then, if it had a left child, move to the left child (this would be it's first child). If it didn't have a left child, move to it's right child (this would be it's next sibling). If it didn't have a left or right child, move up to it's parent (and that parent's parent and so on) until one of those parents has a right child that hasn't been checked yet. You know it hasn't been checked if you just came from a left child, rather than a right child. Pseudo-code:
//Note: Untestedstruct Node{ Node* pParent; Node* pFirstChild; Node* pNextSibling;};void Traverse(Node* pRoot){ Node* pNode = pRoot; while (pNode != NULL) { Visit(pNode); if (pNode->pFirstChild != NULL) { //Start visiting this node's children. pNode = pNode->FirstChild; } else if (pNode->pNextSibling != NULL) { //This node doesn't have any children, but it does // siblings. Let's continue visiting those siblings. pNode = pNode->NextSibling; } else { //This node has no children and is the last sibling. // We're at the end of this branch, so we must work // our way back up to a point where there are siblings // we haven't moved onto yet. while (pNode != NULL) { if (pNode->pPrevious != NULL && //We're not at the root pNode->pPrevious->pFirstChild == pNode && //We're the child of our previous node, rather than a sibling pNode->pPrevious->pNextSibling != NULL) //Our parent has a next sibling { pNode = pNode->pPrevious->pNextSibling; //Time to move on processing nodes rather than // moving back up the tree. break; } else { pNode = pNode->pParent; } } } }}While writing that, though, I thought of a different method that is similar, but has an extra pointer per node, and might be more intuitive. It ends up using a doubly-linked list, primarily so that one can easily distinguish between a node's parent, and a node's previous sibling. The solution above used pPrevious to represent both (previous sibling if there was one, parent if it was the first sibling).
//Again, untestedstruct Node{ Node* pParent; Node* pFirstChild; Node* pPreviousSibling; Node* pNextSibling;};void Traverse(Node* pRoot){ Node* pNode = pRoot; while (pNode != NULL) { Visit(pNode); if (pNode->pFirstChild != NULL) { pNode = pNode->FirstChild; } else if (pNode->pNextSibling != NULL) { pNode = pNode->pNextSibling; } else { while (pNode != NULL && pNode->NextSibling == NULL) { pNode = pNode->pParent; } if (pNode != NULL) { pNode = pNode->NextSibling; } } }}This one is a little bit more simplified because every node can immediately get back to it's parent, instead of having to work it's way through it's previous siblings. This extra parent point could likely come in use in other algorithms, too.
[edit]Of course, as is obvious by the nested while loop, when you've gotten to the bottom, you'll still have to do some work to find the next node that needs processed. But (especially the second example) it's still not too bad. The second example's effort to move to the next node in that situation is merely based upon how many levels up it has to move, and in no way involves the number of sibling nodes that exist on any level whatsoever. In the little scenario you suggested, getting from Node A to Node 3 would take one iteration of the nested while loop, and that's it, because it only had to move up one level.[/edit]
The methods presented are very similiar. Some notable differences are:
With an array of same-level nodes you can access those nodes in reverse order, or even random order should you wish. With a binary tree you can easily go forwards through the same level nodes, or backwards with a tad more work, but not really random access. This isn't really a problem though.
You also get better cache coherrency because of the nodes being in an array and most likely on the same page.
With an array of same-level nodes you can access those nodes in reverse order, or even random order should you wish. With a binary tree you can easily go forwards through the same level nodes, or backwards with a tad more work, but not really random access. This isn't really a problem though.
You also get better cache coherrency because of the nodes being in an array and most likely on the same page.
Topic Locked
This topic has been locked by a moderator. New replies are not allowed.
Sign in to reply to this topic.
Advertisement