ReadTree.txt - Documentation for CPowerTree and CDataNode
| Table of Contents |
| 1. Disclaimer |
| 2. The Idea |
| 3. How it works |
| 4. How to use it |
I am not responsible for what the files will do to your precious computer.
The files didn't destroy my computer, so odds are they won't destroy yours. ^_^
I have no way of knowing is the power tree concept was already thought
of, so don't blame me for getting the credit for creating the power tree.
P.S. (Great minds think alike)
2. THE IDEA
I got 'the idea' from the process of coverting decimal numbers into 1's and 0's.
I figured out (on my own, honest) that to convert a number is to...
1. Find if the number's modulus with 2 equals 0
2. If it is...
a) Add a '0' to the front of a 'list of digits' of some sort.
b) Add a '1' to the front of the list.
3. Divide the number by two 2, rounding down.
4. End when the number is 0
So by this process, you can find the binary code for the number '17'
- - - - - - - - - -
17 mod 2 = 1 => '1'
17 ÷ 2 = 8
8 mod 2 = 0 => '0'
8 ÷ 2 = 4
4 mod 2 = 0 => '0'
4 ÷ 2 = 2
2 mod 2 = 0 => '0'
2 ÷ 2 = 1
1 mod 2 = 1 => '1'
1 ÷ 2 = 0
(End process) @=> 10001
- - - - - - - - - -
I also figured out that a data 'tree', with two brances on each 'node', could store
data and recall it by using it's 'binary address' that would be found using it's decimal address.
Thus the power tree was borne ('power' because it uses the properties of the powers of two to add,
access, and delete nodes, and because the name 'binary tree' was too close to the 'B-tree', which was
created by R. Bayer and E. McCreight in 1972. The B-tree, unlike the power tree, is sorted and uses
indexes and node pages of varrying size to store data.)
(View PowerTree.bmp to see what it looks like and how it works in detail.)
3. HOW IT WORKS
The power tree is implemented by two surprisingly simple classes: CPowerTree and CDataNode.
CPowerTree is the user interface to a recursive structure of CDataNodes. CPowerTree has a single
CDataNode, m_pRoot. It sends functions to m_pRoot, which returns data or performs tasks, like
deleting the last node. CDataNodes have no clue of where they are located in the tree; only CPowerTree
knows the 'shape' of the tree by with its class member m_nSize.
CPowerNode::m_pRoot has two pointers to CDataNodes, m_pLeft and m_pRight, which can point to NULL or
can point to another CDataNode, with two pointers of it's own, and so on and so on... Each CDataNode
has a pointer to a 'whatever-class-you-filled-into-the-template-declaration' named m_pData. CDataNodes
pass calls downward until the right node is found, using the binary algorithm I just showed.
The CPowerNode functions are self explanatory...
RemoveAllPtrs() removes all the CDataNodes without deleting the data, causing a memory leak if the
user doesn't do anything about it. This function can be used to copy pointers to data to a different
container class without copying the data itself.
RemoveLastPtr() removes the last CDataNode in the tree, returning a pointer it's data. Because deleting
a central node is extremely difficult (try rearranging the nodes in CPowerTree.bmp after deleting
node number 3 while keeping the order of the nodes!), I decided to make node deletion work like that
of a stack, where the last node is removed first.
RemoveAndFreeAll() and RemoveAndFreeLast() work like the above two functions, except that the data is also
deleted, avoiding a memory leak.
GetSize() returns the size of the tree.
GetAt(int) and the subscript (  ) operator return a reference to the data at that location. Both functions
work like a zero-starting C-style array.
NOTE: The CPowerTree internally does not count from zero: it increments the argument by 1, simulating
counting from zero.
4. HOW TO USE IT
Because the power tree can hold huge numbers of nodes in a few rows of nodes, it can quickly access
data. The maximum number of recursive calls downward to get data equals n for a tree of size (2^n)-1,
so a tree with 4095 ((2^12)-1) nodes only needs 12 downward calls.
Unfortunately, manipulation of nodes is horrible, and only the last node or ALL nodes can be changed.
I might figure out how to write some creative algorithms to add functionallity for CPowerTree without
relying on STL or MFC collection classes sometime in the future, when CPowerTree 2.0 comes out.