List Tree

sincoder · 08-12-2008, 05:15 AM

What is a List Tree?
It is a data structure that combinds the beauty of a Linked List and Binary Tree.

Why?
The linked-list and binary-tree components of List Tree complement eachother perfectly:
*Iterate through items in a sorted manner. (linked list)
*Search & add new items at logarithmic speed. (binary tree)

What does it look like?

Code:

struct ListTreeItem {
    ListTreeItem *prev, *next; // linked list part
    ListTreeItem *parent, *leftchild, *rightchild; // binary tree part
    void* userdata; // placeholder
};

Background:
I need to implement a TimerManager for a preformance-critical project. My requierments are:
*Keep timers sorted by nearest-in-time -> Solution: linked list
*Add new timers without comparing from-begin-to-end -> Solution: binary tree

I appreciate any feedback. Is this implemented already or is there a better solution?

Cheers
/sincoder

**laserlight** · 08-12-2008, 05:46 AM

It sounds like you want a priority queue, which would typically be implemented using a heap.

**CornedBee** · 08-12-2008, 05:48 AM

Also, linear iteration through a tree is amortized linear time, so the linked list part is unnecessary. More importantly, you don't need the iteration for your use case, so managing the linked list part only adds overhead.

sincoder · 08-12-2008, 06:30 AM

Quote:

Originally Posted by laserlight

It sounds like you want a priority queue, which would typically be implemented using a heap.

Great stuff man. priority_queue is almost exactly what I was looking for. But one thing that's missing, which I didn't mention above. I need to remove any timer (not just the one at the top). Is there any priority_queue with erase() or a good binary heap implementation?

**CornedBee** · 08-12-2008, 07:52 AM

It's not hard to create yourself using the std::heap_* algorithms. Note, however, that the search for a specific element other than the top in a max-heap is linear.

iMalc · 08-12-2008, 01:33 PM

What you've described in your original post is called a "threaded tree".

08-12-2008, 05:15 AM	#1
sincoder Registered User Join Date: Aug 2008 Posts: 2	List Tree - New data structure What is a List Tree? It is a data structure that combinds the beauty of a Linked List and Binary Tree. Why? The linked-list and binary-tree components of List Tree complement eachother perfectly: Iterate through items in a sorted manner. (linked list) Search & add new items at logarithmic speed. (binary tree) What does it look like? Code: struct ListTreeItem { ListTreeItem prev, next; // linked list part ListTreeItem parent, leftchild, rightchild; // binary tree part void userdata; // placeholder }; Background: I need to implement a TimerManager for a preformance-critical project. My requierments are: Keep timers sorted by nearest-in-time -> Solution: linked list Add new timers without comparing from-begin-to-end -> Solution: binary tree I appreciate any feedback. Is this implemented already or is there a better solution? Cheers /sincoder
sincoder is offline

08-12-2008, 05:46 AM	#2
laserlight C++ Witch Join Date: Oct 2003 Location: Singapore Posts: 10,354	It sounds like you want a priority queue, which would typically be implemented using a heap. __________________ C + C++ Compiler: MinGW port of GCC Build + Version Control System: SCons + Bazaar Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
laserlight is online now

08-12-2008, 05:48 AM	#3
CornedBee Cat without Hat Join Date: Apr 2003 Posts: 8,439	Also, linear iteration through a tree is amortized linear time, so the linked list part is unnecessary. More importantly, you don't need the iteration for your use case, so managing the linked list part only adds overhead. __________________ All the buzzt! CornedBee "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code." - Flon's Law
CornedBee is offline

08-12-2008, 07:52 AM	#5
CornedBee Cat without Hat Join Date: Apr 2003 Posts: 8,439	It's not hard to create yourself using the std::heap_* algorithms. Note, however, that the search for a specific element other than the top in a max-heap is linear. __________________ All the buzzt! CornedBee "There is not now, nor has there ever been, nor will there ever be, any programming language in which it is the least bit difficult to write bad code." - Flon's Law
CornedBee is offline

08-12-2008, 01:33 PM	#6
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,475	What you've described in your original post is called a "threaded tree". __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
question about a working linked list	cold_dog	C++ Programming	23	09-13-2006 01:00 AM
HUGE fps jump	DavidP	Game Programming	23	07-01-2004 10:36 AM
How can I traverse a huffman tree	carrja99	C++ Programming	3	04-28-2003 05:46 PM
singly linked list	clarinetster	C Programming	2	08-26-2001 10:21 PM