red-black tree data structure
Hi, It's not really a Python-related question, sorry for that. Does anyone know why red-black trees got these colors in their names? Why not blue-orange for instance? I'm just curious. Thanks, Laszlo -- http://mail.python.org/mailman/listinfo/python-list
Re: red-black tree data structure
On Wed, Apr 11, 2012 at 11:14 AM, Jabba Laci jabba.l...@gmail.com wrote: Hi, It's not really a Python-related question, sorry for that. Does anyone know why red-black trees got these colors in their names? Why not blue-orange for instance? I'm just curious. http://programmers.stackexchange.com/questions/116614/where-does-the-term-red-black-tree-come-from -- http://mail.python.org/mailman/listinfo/python-list
Re: red-black tree data structure
Hi, Thanks for the answer. I copy the solution here: According to wikipedia: The original structure was invented in 1972 by Rudolf Bayer and named symmetric binary B-tree, but acquired its modern name in a paper in 1978 by Leonidas J. Guibas and Robert Sedgewick. Answer from Professor Guidas: from Leonidas Guibas gui...@cs.stanford.edu to of the Red-Black term mailed-by cs.stanford.edu hide details 16:16 (0 minutes ago) we had red and black pens for drawing the trees. Laszlo On Wed, Apr 11, 2012 at 19:39, Ian Kelly ian.g.ke...@gmail.com wrote: On Wed, Apr 11, 2012 at 11:14 AM, Jabba Laci jabba.l...@gmail.com wrote: Hi, It's not really a Python-related question, sorry for that. Does anyone know why red-black trees got these colors in their names? Why not blue-orange for instance? I'm just curious. http://programmers.stackexchange.com/questions/116614/where-does-the-term-red-black-tree-come-from -- http://mail.python.org/mailman/listinfo/python-list
Re: red-black tree data structure
Bringing this back to Python a bit: http://newcenturycomputers.net/projects/rbtree.html http://pypi.python.org/pypi/bintrees/0.3.0 http://pypi.python.org/pypi/treap/0.995 Red-Black trees are supposed to be slower than treaps on average, but they're also supposed to have a lower standard deviation in execution times compared to treaps. So for batch processing, the treap might be better, while for use in an interactive application, red-black trees might be better - because for batch processing no one cares about a little jerkiness, while in an interactive app it might annoy users. Apparently there was an effort, briefly, to get a red-black tree into Python's collections module, but it was rejected. Treaps are supposed to have a simpler implementation than red-black trees. I'm amused by the red and black pens thing. ^_^ On Wed, Apr 11, 2012 at 10:14 AM, Jabba Laci jabba.l...@gmail.com wrote: Hi, It's not really a Python-related question, sorry for that. Does anyone know why red-black trees got these colors in their names? Why not blue-orange for instance? I'm just curious. Thanks, Laszlo -- http://mail.python.org/mailman/listinfo/python-list -- http://mail.python.org/mailman/listinfo/python-list
Re: Tree data structure with: single, double and triple children option along with AVM data at each node
There a many ways to do this, here's one:
from collections import namedtuple
Tree = namedtuple('Tree', ['feature', 'children'])
t = Tree(1, [Tree('hello', []), Tree(3, [])])
--
http://mail.python.org/mailman/listinfo/python-list
Tree data structure with: single, double and triple children option along with AVM data at each node
Dear sir, I am very happy to find this group. Sir, i am new to Python. Currently i am working on text processing. Can you give me some suggestions about Tree data structure representation, where i require each node capable to handle: only one child, or up to 3 children plus hold feature information. Thanking you, L. Nirman Singh -- http://mail.python.org/mailman/listinfo/python-list
Re: Recommendations on Pythonic tree data structure design techniques
En Thu, 09 Apr 2009 13:18:27 -0300, pyt...@bdurham.com escribió: Any recommendations on Python based tree data structures that I can study? I'm working on an application that will model a basic outline structure (simple tree) and am looking for ideas on Pythonic implementation techniques. I'd use ElementTree. An Element is a generic container for hierarchical data - doesn't have to be XML. See http://effbot.org/zone/element-index.htm and http://docs.python.org/library/xml.etree.elementtree.html -- Gabriel Genellina -- http://mail.python.org/mailman/listinfo/python-list
Recommendations on Pythonic tree data structure design techniques
Any recommendations on Python based tree data structures that I can study? I'm working on an application that will model a basic outline structure (simple tree) and am looking for ideas on Pythonic implementation techniques. By outline I mean a traditional hierarchical document outline (section, chapter, sub-chapter, ...). I will be building this structure as I parse my customer's internally designed (proprietary) publishing markup language. My initial thought is to implement a generic node container class with attributes for parent, next, previous, and child 'pointers'. The node objects will be stored in a dictionary where node 'pointers' correspond to incrementally assigned numeric keys. Thanks! Malcolm -- http://mail.python.org/mailman/listinfo/python-list
Re: Recommendations on Pythonic tree data structure design techniques
Any recommendations on Python based tree data structures that I can study? I'm working on an application that will model a basic outline structure (simple tree) and am looking for ideas on Pythonic implementation techniques. By outline I mean a traditional hierarchical document outline (section, chapter, sub-chapter, ...). I will be building this structure as I parse my customer's internally designed (proprietary) publishing markup language. My initial thought is to implement a generic node container class with attributes for parent, next, previous, and child 'pointers'. The node objects will be stored in a dictionary where node 'pointers' correspond to incrementally assigned numeric keys. http://www.google.com/search?q=python+tree+data+structure HTH, Daniel -- Psss, psss, put it down! - http://www.cafepress.com/putitdown -- http://mail.python.org/mailman/listinfo/python-list
Re: Recommendations on Pythonic tree data structure design techniques
I'm writing a Python graph library (called Graphine) that's pretty easy to use and does what you want. It is pre-alpha right now, but if you're interested please let me know- I'm very interested in hearing outside opinions. -- http://mail.python.org/mailman/listinfo/python-list
Re: Recommendations on Pythonic tree data structure design techniques
pyt...@bdurham.com wrote: Any recommendations on Python based tree data structures that I can study? I'm working on an application that will model a basic outline structure (simple tree) and am looking for ideas on Pythonic implementation techniques. By outline I mean a traditional hierarchical document outline (section, chapter, sub-chapter, ...). I will be building this structure as I parse my customer's internally designed (proprietary) publishing markup language. My initial thought is to implement a generic node container class with attributes for parent, next, previous, and child 'pointers'. That sounds reasonable, but do you need parent? It creates a reference loop, which make GC less likely to happen (or at least later), and it also complicates adding and removing nodes. Many algorithms don't need it. Even if you do need to ascend the tree you may be able to get by with a path that is a list of nodes from root to the current node and that indexes the node. The node objects will be stored in a dictionary where node 'pointers' correspond to incrementally assigned numeric keys. This doesn't make sense to me. It sounds like you are re-inventing lists (arrays). Andrew -- http://mail.python.org/mailman/listinfo/python-list
Re: tree data structure
couple of links for python tree: http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/217212 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/201423 http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/305313 http://www.rexx.com/~dkuhlman/ -- http://mail.python.org/mailman/listinfo/python-list
tree data structure
Hi! all i am a new member on this list. I have to implement tree data structure using python. How it can be done in python. Is there an existing data structure which can be used as tree? I have searched archives and manuals but no luck. Regards VK Hug the REALITY ;-) Disclaimer The facts expressed here belong to everybody, the opinions to me. The distinction is yours to draw... __ Do you Yahoo!? Yahoo! Small Business - Try our new resources site! http://smallbusiness.yahoo.com/resources/ -- http://mail.python.org/mailman/listinfo/python-list
Re: tree data structure
vivek khurana wrote: Hi! all i am a new member on this list. I have to implement tree data structure using python. How it can be done in python. Is there an existing data structure which can be used as tree? Tuples can be used as trees: you can let them represent (data, left_child, right_child). # a binary search tree for the integers 0 to 6 (3, (1, (0, None, None), (2, None, None)), (4, (5, None, None), (6, None, None))) -- http://mail.python.org/mailman/listinfo/python-list
Re: tree data structure
Hi,
You could use Python dictionaries as trees. Example:
to represent a simple tree:
'a' - ( 'b' , 'c' )
'b' - ( 'd', 'e', 'f')
'e' - ( 'g')
'f' - ('h', 'i', 'j')
treeD = { 'a' : (
{ 'b' : (
'd',
{ 'e' : 'f' },
{f : ( 'h', 'i', 'j' )}
)
},
'c'
)
}
hope this helps.
regards,
Satchit
Satchidanand Haridas (sharidas at zeomega dot com)
ZeOmega (www.zeomega.com)
Open Minds' Open Solutions
#20,Rajalakshmi Plaza,
South End Road,
Basavanagudi,
Bangalore-560 004, India
vivek khurana wrote:
Hi! all
i am a new member on this list. I have to implement
tree data structure using python. How it can be done
in python. Is there an existing data structure which
can be used as tree? I have searched archives and
manuals but no luck.
Regards
VK
Hug the REALITY ;-)
Disclaimer
The facts expressed here belong to everybody, the opinions to me. The
distinction is yours to draw...
__
Do you Yahoo!?
Yahoo! Small Business - Try our new resources site!
http://smallbusiness.yahoo.com/resources/
--
http://mail.python.org/mailman/listinfo/python-list
Re: tree data structure
vivek khurana wrote: i am a new member on this list. I have to implement tree data structure using python. How it can be done in python. Is there an existing data structure which can be used as tree? I have searched archives and manuals but no luck. You can start with Guido's essay http://python.org/doc/essays/graphs.html /mr -- http://mail.python.org/mailman/listinfo/python-list
