implementing binary trees - data structure, trie

Question

Binary trees. The principal is understandable, but what do they really looks like in terms of arrays or associative arrays?

if the data structures I have available to me are:

AssociativeArray={tag:value,tag:value,tag:value} 

(of course, each tag is unique)

and

Array=[value,value,value] 
(where the value can be any data type including array)

examples:

DictOfWords={greeting:"hello",sound:"music",sleep:"dream",words:["hello","music","dream"]}
listOfWords=["hello","music","dream",DictOfWords]

what would a binary tree built out of one or both of those look like?

further, what would the data structure for a trie for word search look like built from those data structures?

What would a node of a trie look like? Would it be an Associative Array or a linear array or some combination of the two? I understand from this post that "A trie holds one node per character"

so would the top level structure be something like:

trie={a:{},b:{},c:{}...}

or

trie={a:[],b:[],c:{}...}

or

trie=["a","b","c"...]

Answer 1

Tries and Binary Trees are usually not thought of as arrays or associative arrays. They are thought of as collections of nodes, usually implemented as a struct. For example, binary trees tend to look like

struct BTreeNode
{
    value_type value;
    BTreeNode* left;
    BTreeNode* right;
};

And Tries tend to look like

struct TrieNode
{
    char_type  letter;
    associative_array<char_type, TrieNode*> children;
};

Now if you are only looking to model this with arrays and associative arrays, the question is going to be: what do you intend to do with them? If all you need to do is store data in a tree/trie structure, you have a lot of options. However, if you actually want to use a BTree as a BTree or a Trie as a Trie, we have to make sure that whatever transformation you use to convert structures to arrays/associative arrays works. The easiest one: treat each struct as an associative array with a constant number of entries

    4
   / \
  2   5
 / \   \
1   3   6

Would be usually done as

BTreeNode oneNode(1, null, null);
BTreeNode threeNode(3, null, null);
BTreeNode twoNode(2, oneNode, threeNode);
BTreeNode sixNode(6, null, null);
BTreeNode fiveNode(5, null, sixNode);
BTreeNode fourNode(4, twoNode, fiveNode);

You can do a 1-to-1 conversion of those structs to associative arrays and get

fourNode = {   value: 4,
               left: {
                   value: 2,
                   left: {
                       value: 1
                   },
                   right: {
                       value: 3
                   }
               },
               right: {
                   value: 5,
                   right: {
                       value:6
                   }
              }
          }

There is a comparable conversion to arrays, but it is less obvious to read

A comparable trie storing "abc" "abd" "abe" "ace" creates a trie structure that looks like

    a
   / \
  b    c
/ | \   \

c d e e

Doing the same conversion from structs to values as above, you get

trie =  {
            letter: 'a',
            children: {
                'b': {
                    letter: 'b'
                    children: {
                        'c': { letter: 'c' },
                        'd': { letter: 'd' },
                        'e': { letter: 'e' }
                    }
                'c': {
                    letter: 'c'
                    children: {
                        'e': { letter: 'e' }
                    }
            }
       }

However, standing by my original comments, "what do they really looks like in terms of arrays or associative arrays?" is unanswerable. They don't actually get implemented as arrays or associative arrays at all, so "really look like" cannot be used alongside "arrays or associative arrays." Think of them in terms of the node structures that they are really constructed from, and you will go much further.

For example, there is an idea of a self balancing binary tree. Those structures are very easy to understand if you think of the structures as a bunch of nodes linked together. If you try to think of a self balancing binary tree in terms of arrays/associative arrays, you will have a LOT of trouble, because they tend to have a pointer back to their parent, which creates really messed up looking associative arrays.

struct SelfBalancingBTreeNode
{
    value_type value;
    SelfBalancingBTreeNode* parent;
    SelfBalancingBTreeNode* left;
    SelfBalancingBTreeNode* right;
};

To model this you need to have really interesting associative array structures

leftNode = { value: 1, parent: null, left: null, right: null}
parentNode = value: 2, parent: null, left: leftNode, right: null}
leftNode['parent'] = parentNode

Which creates cycles that are not commonly thought of when using associative arrays

Answer 2

Binary tree:

     1
   /   \
  2     3
 / \   / \
4   5 6   7

Can be represented as:

[1, 2, 3, 4, 5, 6, 7]

Thus a node at index i's children are at indices 2i and 2i+1.

Or it can be represented as:

{1:[2,3], 2:[4,5], 3:[6,7]}

With a reference to the root somewhere.

Trie:

      1
  a /   \ b
   2     3
a / \ b
 4   5

Can be represented as:

{1:{a:2, b:3},
 2:{a:4, b:5},
 3:{},
 4:{},
 5:{}
}