Description: QTreeViewer is a small application for working with binary search tree (BST). My aim was to make a BST Viewer, but it seems to be a BST Editor right now =)
This is my first quite good qApp. The main purpose was to take a closer look at Qt and to make smth interesting (but maybe not very useful) at the same time.
Features: * adding values to the tree (there is a batch mode for adding a group of values); * removing values from the tree (you can either select some nodes and delete them, or remove particular value - if this value exists in the tree it'll be found and deleted); * zoom for more comfortable work with the tree (Ctrl+wheel works too); * "smart" positioning algorithm, that makes tree compact without breaking its structure.
It's just an educational app without any practical usage, but I like it and Qt that allows to implement all my ideas.
I'll be very happy to get any comments about design, implementation, my code style or about the program itself. Without any comments in the code (I'm sorry) it might be not very easy to understand the algorithm, that place nodes, but I'll be grateful if you can suggest smth that can improve this program and my code.Last changelog:
3.5 - Now QTreeViewer is compatible with Qt 4.6.
3.4 - Small design improvement: glow around the node on mouse over.
3.3 - You can find value by index now. This operation is optimized - it takes approximately ln(n) operations (O(ln(n)) complexity). - Gradient node background =)
3.2 - Fixed bug in quick adding panel validator (it accepted input like '12-13' without any spaces in previous version). - You can rotate nodes now. The rotation is not clear enough, but it acts like rotation while RBTree balancing. - Some improvements in the implementation. Node functionality is much more easy now. - Small design improvement - node scaling on mouse hover =) It's not smooth right now, but I'll work on it. - Rotate and delete actions are enabled only when they're appropriate.
3.1 - Fixed bug with negative numbers in batch mode. - Added quick panel in the status bar. It has validator and can add multiple values.
Looks like a useful app. I remember writing similar applications during my studies some years ago. One thing that changed since then: node pointers are now most likely 64 bit and node payload therefore doesn't matter that much anymore.
Things I'm missing:
* scroll wheel zoom
* node rotation via context menu
Some pointers from my sources:
* http://trac.cyblogic.com/libPONA/browser/pona/BinaryTree.hpp
* http://trac.cyblogic.com/libPONA/browser/pona/AvlTree.hpp
One thing I really would love to explore with binary trees is keeping node counts with each node. Each node would store the number of nodes in its subtree and thereby would allow O(n)=c*ld(n) random access on the tree. Of cause such node counts would need to be updated during insertions/rotations...
And what about clustering nodes to memory pages, well ... I'm day dreaming.
Things I'm missing:
* scroll wheel zoom
* node rotation via context menu
How about Ctrl+wheel? Unfortunately, I'm a single-OS user, but Ctrl+wheel works fine for me on WinXP.
About rotations.
Do you mean rotations like in Red-Black Trees? It'll be a good idea to perform a rotation... It'd be better to implement red-black tree, but I'm not interested in them right now =)
Quote:
One thing I really would love to explore with binary trees is keeping node counts with each node. Each node would store the number of nodes in its subtree and thereby would allow O(n)=c*ld(n) random access on the tree. Of cause such node counts would need to be updated during insertions/rotations...
Storing and updating subtree size for every node is not difficult and it's a good information. The app dont count it right now, but maybe I'll add it into the next release. =)
Anyway random access (e.g., while removing node by value) is performing for O(h), where h = tree height, so it's O(ld(n)). Am I right?
And what is 'clustering nodes'? I'm quite familiar with tree algorithms, but not in English =(
Rotations allow equivalent transformation of the tree. There are only two rotations defined. I remember it was quite fun to invoke rotations by clicking on nodes and watching the structure to change. This allowed me to develop a natural understanding of tree balancing algorithms... But where I left the code?... hmmm...
When talking about random access I was thinking about index access. When you know the number of elements in the left and right subtree you can easily decide where to go, if you are looking for the n-th element stored in a tree. Yes, traversing from the root takes O(n)=h.
I know, how to perform rotation =)
And I understand your idea about index access. I'll try to implement that all.
And what about clustering? I really dont know, what is this... =(
"Clustering" is an invention of mine. I took a B-tree (B for block or Bayer?) and sorted the elements stored with each node. Because the elements were stored in sorted arrays I could use binary search to lookup an element by value... At this point the access pattern looks like a binary tree lookup and the question opens up if I could go the other way round. Take a binary tree and align the elements stored in a subtree to a memory page.
The most common issue with binary trees is that they don't scale to virtual memory, which could be solved at this point.
By the way, the same holds true for in-memory hashes. Reading the binary number along the search path gives nothing more than a perfect hash sum. For instance the Ruby gems package manager fails on systems with low memory because of using hashes that don't scale in memory.
Also when paging out a subtree it could be stored as a sorted array, greatly increasing the memory density of the binary tree. For read-only access you wouldn't need to unpack the array -- simply go with sequential read or binary search.
Anyway, that's all part of my theory dream worlds and I have practically no time time to follow those paths...
For my study papers I was used to take graphviz. Having some graphviz style data import and printing would be nice, too.
Ratings & Comments
5 Comments
Looks like a useful app. I remember writing similar applications during my studies some years ago. One thing that changed since then: node pointers are now most likely 64 bit and node payload therefore doesn't matter that much anymore. Things I'm missing: * scroll wheel zoom * node rotation via context menu Some pointers from my sources: * http://trac.cyblogic.com/libPONA/browser/pona/BinaryTree.hpp * http://trac.cyblogic.com/libPONA/browser/pona/AvlTree.hpp One thing I really would love to explore with binary trees is keeping node counts with each node. Each node would store the number of nodes in its subtree and thereby would allow O(n)=c*ld(n) random access on the tree. Of cause such node counts would need to be updated during insertions/rotations... And what about clustering nodes to memory pages, well ... I'm day dreaming.
At first, thanks for comment =) And now... Quote:Things I'm missing:
* scroll wheel zoom
* node rotation via context menu
How about Ctrl+wheel? Unfortunately, I'm a single-OS user, but Ctrl+wheel works fine for me on WinXP.
About rotations.
Do you mean rotations like in Red-Black Trees? It'll be a good idea to perform a rotation... It'd be better to implement red-black tree, but I'm not interested in them right now =)
Quote:One thing I really would love to explore with binary trees is keeping node counts with each node. Each node would store the number of nodes in its subtree and thereby would allow O(n)=c*ld(n) random access on the tree. Of cause such node counts would need to be updated during insertions/rotations...
Storing and updating subtree size for every node is not difficult and it's a good information. The app dont count it right now, but maybe I'll add it into the next release. =)
Anyway random access (e.g., while removing node by value) is performing for O(h), where h = tree height, so it's O(ld(n)). Am I right?
And what is 'clustering nodes'? I'm quite familiar with tree algorithms, but not in English =(
Rotations allow equivalent transformation of the tree. There are only two rotations defined. I remember it was quite fun to invoke rotations by clicking on nodes and watching the structure to change. This allowed me to develop a natural understanding of tree balancing algorithms... But where I left the code?... hmmm... When talking about random access I was thinking about index access. When you know the number of elements in the left and right subtree you can easily decide where to go, if you are looking for the n-th element stored in a tree. Yes, traversing from the root takes O(n)=h.
I know, how to perform rotation =) And I understand your idea about index access. I'll try to implement that all. And what about clustering? I really dont know, what is this... =(
"Clustering" is an invention of mine. I took a B-tree (B for block or Bayer?) and sorted the elements stored with each node. Because the elements were stored in sorted arrays I could use binary search to lookup an element by value... At this point the access pattern looks like a binary tree lookup and the question opens up if I could go the other way round. Take a binary tree and align the elements stored in a subtree to a memory page. The most common issue with binary trees is that they don't scale to virtual memory, which could be solved at this point. By the way, the same holds true for in-memory hashes. Reading the binary number along the search path gives nothing more than a perfect hash sum. For instance the Ruby gems package manager fails on systems with low memory because of using hashes that don't scale in memory. Also when paging out a subtree it could be stored as a sorted array, greatly increasing the memory density of the binary tree. For read-only access you wouldn't need to unpack the array -- simply go with sequential read or binary search. Anyway, that's all part of my theory dream worlds and I have practically no time time to follow those paths... For my study papers I was used to take graphviz. Having some graphviz style data import and printing would be nice, too.