Sign in to follow this  

efficiently inserting nodes into a binary search tree using linked lists?

This topic is 4691 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a question. I programmed a binary search tree and I'm trying to think of some applicable uses for it. the most obvious one I thought of was storing vertices for different models to be loaded in a game. here's the question. would it be possible to make a linked list of bst node functions and load all of the vertices into the data pointer of each node from a .txt file? it seems plausible, but I don't know how to do it if it will work. I would have each node of the bst loaded into a linked list, and then insert the nodes into the bst by traversing the linked list and inserting each node into the tree after calling "node_next(*node)". if you have any suggestions or just feel like slapping me because I am an idiot for thinking of this, please reply. thanks

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
I'm probably completely missing your point, but how does a binary search tree relate to storing model vertices?

I don't understand the part where you say you want to "have each node of the BST loaded into a linked list" and then "insert the nodes into the BST". Can you provide an example of what you're tyring to do?

It sounds like you should really just store a pointer to the data that you're interested in with each node in the BST. Again, I don't know what you're trying to do but storing the same information in a linked list as well as in the BST seems unnecessary.

Anyway, like I said, I'm probably misunderstanding your message and what you're trying to do so I'm sorry if this isn't of much help.

Share this post


Link to post
Share on other sites
ok, that did sound really redundant. sorry. ok. I'll give a new example. I want my binary search tree to have nodes for every sprite in a 2d game. I will use the tree to properly render the sprites depending on their y-value. now for the other part about the linked list. what I meant to say was, instead of manually creating each node per sprite and inserting them all into the tree, I want to store all of the sprites' information into a .txt file and then load the information from the .txt file into a linked list. Then I would be able to create each node for my tree by recursively calling a function "bistree_insert(LinkList *sprite_list)". Inside the function, I would set it up so that after a node was created for the current position in my linked list, it would call "bistree_insert(sprite_list->next) to create the next node. The reason I would do this is so that I don't have to create a tree node structure for every object in my game, and have to use a "for" loop just to insert each node into the tree. I hope this makes a little more sense. it did while I was typing it lol.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Everything you're saying seems fairly reasonable and I don't see why you wouldn't or shouldn't do it that way. The only thing I would say is that unless you have a reason for having the sprites loaded into a linked list then you might want to get rid of that linked list altogether and load directly into the BST.

You already have some kind of routine that builds the linked list from your data file(s) so it should be pretty simple to modify that to insert into the BST instead of into the linked list.

But it's not that important either way. If you want to keep the linked list around and that's already working then yes, you could just iterate over the list and insert into the BST assuming the insert function knows to order on your Y value.

Share this post


Link to post
Share on other sites
great, thanks for the reply. I had assumed that the idea would work, I just needed some reassurance. I think I will take out the linked list because the added O(n) from travesing the linked list will reduce the efficiency of the rendering per game frame. thanks again!

Share this post


Link to post
Share on other sites
One thing to note is that if your list is in order then the standard way of inserting them into a binary tree results in a linked list. The first node is the root and each subsequent node goes to the rightmost position of the tree. So if you know you are building from an ordered list you build from the bottom up.

Share this post


Link to post
Share on other sites
Lilbudywizer: having a list as the tree would only happen when using a naïve implementation. Most of the time, implementations go around this problem by balancing the tree (using a splay tree, for instance, although Red-Black or B-trees also work).

CreepingDeath666: I somehow feel that there would be an overhead for storing your objects in both a tree and a list. The two methods I use most of the time are:

- Keeping a vector, keeping it sorted with insertion sort, which is more or less O(n) on an almost sorted container, which yours will be most of the time. Insertion can be done in O(n) as well (find where to insert, insert).

- Keeping a plain list of objects, and using radix sort every frame to sort it (assuming you have access to the actual nodes of the list, you can even optimize this so you only change pointer values).

Share this post


Link to post
Share on other sites
The purpose of using a bst is to speed up random lookups of items, and to keep data sorted. However, a simple ordered bst is not the best for that, as it can degenerate into a linked list with data inserted in consecutive order (as would be the case when reading them from an ordered list). Bst's only work ok if inserts are pretty much in random order. Your ideas so far for how to use it aren't the most appropriate uses.

A better bst is the reasonably simple to understand AVL-Tree, or the slightly harder Red-Black-Tree, as is popular with STL implementations. Red-Black-Trees are essentially a simplified implementation of 2-3-4-Trees. AA-Trees, are another less well known bst, and are about as good as AVL & RB trees.

For data where some items are accessed more frequently than others, the caching properties of a splay tree make it very useful. For example, storing a dictionary in memory for spell-checking would be a good use for a splay tree.
I have implemented all of the above myself (although I haven't finished the 'remove' for an AA-tree yet).

And when it comes to storing trees in a fairly compressed way, and for storage on disk or flash RAM, look into B-trees.

btw, there is a name for a data-structure where each item is stored in a list and a tree simultaneously, it's called a 'Threaded tree'.

If you're quite interested in binary search trees, take a look at libAvl and BinaryTreesome.
You may also be interested in the array binary search algorithm, which is better for data that doesn't change very much, due to it's zero memory overhead.

Nowdays I'm getting away from using bst's, and using hash-tables instead which are even faster again, in most cases. (When I don't need to access the items in order of course [smile]).

If you ask nicely, I may even share some of my nice bst code, including a non-recursive ordinary-bst insert.

Share this post


Link to post
Share on other sites
Thanks for the great ideas ToohrVyk. I think I'll use the radix sort since I do have access to the nodes and information. that will be much faster than having to balance the tree jsut to keep the effiency relatively good. thanks again! And,iMalc, I would love to see that code for the non-recursive insert. I tried so many times to implement that efficiently but never could. I've been looking into chained Hash Tables as well, and yeah, I see what you're saying about how using a BST in this situation wouldn't be wise. First of all, yeah, it would be a hassle and a waste of time having to keep the tree balanced, and also, the sprites I would be storing are moving sprites, so their y-values would be constantly changing making it really unefficient to store the sprite info in a tree. thanks again!

Share this post


Link to post
Share on other sites
Here it is:
Depending on whether you want it to allow duplicates or not, you can define ALLOW_DUPLICATES.
template <class TNode>
void TreeInsert(TNode *&head, TNode *ins) {
TNode *curr = head;
ins->left = ins->right = NULL;
if (head == NULL) {
head = ins;
} else do {
if (*ins < *curr) {
//it goes somewhere in the left sub-tree
if (curr->left == NULL) {
curr->left = ins;
break;
}
curr = curr->left;
} else
#ifndef ALLOW_DUPLICATES
if (*curr < *ins)
#endif
{
//it goes somewhere in the right sub-tree
if (curr->right == NULL) {
curr->right = ins;
break;
}
curr = curr->right;
}
#ifndef ALLOW_DUPLICATES
else {
// 'ins' is in the tree already; do nothing
break;
}
#endif
} while (true);
}
Enjoy!

Share this post


Link to post
Share on other sites
You certainly have to call it once for each node you wish to insert. You would obviously use a simple loop for this if you have a lot to insert at once. There is no need to recurse for that though. The function as written also relies on caller allocation, btw.

You could use it like this to sort an array for example (not that I'm suggesting that would be a good usage):
template <class T>
struct Node {
Node *left, *right;
T item;
inline bool operator < (const Node &rhs) { return item < rhs.item; }
};

template <class T, class Size, class TNode>
void TreeDumpToArray(T a[], Size &idx, TNode *node) {
while (node != NULL) {
TreeDumpToArray(a, idx, node->left);
a[idx++] = node->item;
node = node->right;
}
}

template <class T, class Size>
void BinaryTreeSort(T a[], Size n) {
Size idx=0;
Node<T> *head=NULL, *const buf = (Node<T>* const)malloc(sizeof(Node<T>) * n);
for (Size i=0; i<n; ++i) {
buf[i].item = a[i];
TreeInsert(head, &buf[i]);
}
TreeDumpToArray(a, idx, head);
free(buf);
}

int main() {
int foobar[8];
for (int i=0; i<8; ++i)
foobar[i] := rand()%100;
BinaryTreeSort(foobar, 8);
for (int i=0; i<8; ++i)
cout << foobar[i] << endl;
}

Minimal use of recursion again, as you can see.

Share this post


Link to post
Share on other sites
Uhh, I might have missed something. How do you plan to store vertices in a BST?
The application isn't very useful. You might want to now code a BSP tree which is much more useful for 3d geometry.

If you want to find something to do with your BST make a symbol table or use it for parsing text.

If you want to have more fun now implement red-black trees and avl-trees. These are BSTs which will approximate a balanced tree in different ways. These are usually more useful than a simple BST because you are guaranteed (most of the time) faster lookups.

Share this post


Link to post
Share on other sites

This topic is 4691 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this