[ Ссылка ]
—
Presentation Slides, PDFs, Source Code and other presenter materials are available at: [ Ссылка ]
—
The binary tree is perhaps the most important non-linear data structure and yet there is no standard implementation, or implementation in Boost for that matter.
There are third-party library implementations such as in tree.hh by Kasper Peeters, or buried in a geometry library such as Pastel, but they doesn't have the rich graph theoretic concepts and algorithms established in Boost.Graph and they're designed as containers (using node-based allocation).
Boost.Graph has the compressed_sparse_row_graph, but it's not mutable and it doesn't have any binary tree concepts.
So this is the story of making a fresh generic binary tree implementation for Boost.Graph: satisfying the MutableGraph and BidirectionalGraph concepts whilst being competitive in performance to compressed_sparse_row_graph. (VertexListGraph is a work in progress.)
It's an unfinished story that is a few chapters in but probably needs your help to finish telling it.
As we know, a binary tree is a (very) special case of tree and it receives special attention in two particular books of note: The Art of Computer Programming by Donald Knuth and Elements of Programming by Alexander Stepanov & Paul McJones. It's from these two books that the bulk of the algorithms and data structures for a binary tree come from.
What's not in those books is how to put it all together in a single, efficient design. Although ostensibly the simplest non-linear data structure, a binary tree has a few significant design options on which it can be parameterized: trade-offs in achieving this through different class designs will be explored.
The structure too can be stored in various different ways, which will also be explored and ultimately compared for performance.
I'd like to leave a good chunk of time at the end for discussion on future directions, pathways to a standard graph library, etc.
—
Jeremy Murphy
ResMed
Senior Software Engineer
Sydney, Australia
Jeremy started programming 25 years ago in C and finally discovered C++ in the C++0x days. He is interested in computational geometry, graph theory and the related data structures and algorithms. He has worked on molecular modelling, telecommunication network optimization, motion reconstruction and now embedded devices in the medical field.
—
Videos Filmed & Edited by Bash Films: [ Ссылка ]
---
*--*
---
