B.Sc. Diploma Work

Sunday, June 06, 2010 » programming, uni

After my Bachelor studies came the compulsory task to creating something "large" software and writing his user and developer manuals. My purpose was to create a binary tree visualization program in C++ in QT Open Source Edition 4.5.0 (using QT Creator 1.0.0 and QT Design 4.5.0). It was able to display the operations and his different orders of binary search tree, AVL tree and red-black tree in pretty visualization to make the operations understand with the user. The only challenge was the correct visualization of the trees and his leafs - not going out of the window and keeping the tree as small as possible for the appropiate visualization depends on the shape of tree.

Drawing algorithm:

The aim was to keep as big part of tree as possible on the screen and minimalizing the usage of panes but still keeping the shape of binary tree. The shape of tree is only modificated in case of insert and remove, the binary-shape-correction algorithm (BSCA) must be called after these operations.

Every new vertex must be inserted with C1 distance from his parent along the x-axe, and move with C2 distance along y-axe. When it's ready let's call the BSCA algorithm:

Do while there is collision in the tree:
- start move from the root in consecutive order (it can be realized with queue) and store the currently placed B item and his previous item A (in manner of consecutive order)
- when A and B are on the same level, A and B have intersection => go back to the common parent then shift the left and right partial tree until the collision has eliminated
- when the there is no more intersection, continue the consecutive ordering until the whole tree is processed and there is no more collision

This way the BSCA expanding his partial trees, in case of large number vertices keeping the on the screen as possible.

Program for user perspect:

Drop a mail to access.
[ bsc_diploma_work_2008.pdf ]