11/3 DS Review

Introduction of Tree

A tree data structure:

1. A finite set of one or more nodes that stores hierarchical data.
2. Must include a root node.
3. Remaining nodes are disjoint sets, which form subtrees.

\(U\)(Universal Set): \(\{A, B, C, D, E\}\)

digraph BST {
    node [fontname="Arial" ];
    a [label = "A"];
    b [label = "B"];
    c [label = "C"];
    d [label = "D"];
    e [label = "E"];
}

digraph BST {
    node [fontname="Arial" ];
    a [label = "A"];
    b [label = "B"];
    c [label = "C"];
    d [label = "D"];
    e [label = "E"];
    
    a -> b;
    a -> c;
    c -> d;
    c -> e;
}

digraph BST {
    node [fontname="Arial" ];
    a [label = "A"];
    b [label = "B" style=filled, fillcolor=green];
    c [label = "C" style=filled, fillcolor=yellow];
    d [label = "D" style=filled, fillcolor=yellow];
    e [label = "E" style=filled, fillcolor=yellow];
    
    a -> b;
    a -> c;
    c -> d;
    c -> e;
}

\(S_b: \{B \}\)
\(S_c: \{C, D, E\}\)

Disjoint: \(S_b \cap S_c = \varnothing\)

Terminology

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" xlabel = "degree: 3", front="" style=filled, fillcolor=red];
    lb [ label = "B" xlabel = "degree: 2", front="" style=filled, fillcolor=yellow];
    lc [ label = "C" ];
    ld [ label = "D" ];
    le [ label = "E" ];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" xlabel = "degree: 0", style=filled, fillcolor=green ];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

Degree: the number of subtrees of a node.

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" style=filled, fillcolor=red, xlabel="root node"];
    lb [ label = "B" style=filled, fillcolor=yellow, xlabel = "internal node"];
    lc [ label = "C" ];
    ld [ label = "D" ];
    le [ label = "E" ];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" style=filled, fillcolor=green xlabel = "leaf node"];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

Internal(non-terminal) node; Leaf(terminal) node

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" xlabel = "parent" style=filled, fillcolor=red];
    lb [ label = "B" xlabel = "children" style=filled, fillcolor=yellow];
    lc [ label = "C" style=filled, fillcolor=yellow];
    ld [ label = "D" style=filled, fillcolor=yellow];
    le [ label = "E" ];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" ];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" ];
    lb [ label = "B" xlabel = "siblings" style=filled, fillcolor=yellow];
    lc [ label = "C" style=filled, fillcolor=yellow];
    ld [ label = "D" style=filled, fillcolor=yellow];
    le [ label = "E" ];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" ];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

Node B, C, D have the same parent.

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" xlabel="ancestor" style=filled, fillcolor=brown];
    lb [ label = "B" xlabel = "ancestor" style=filled, fillcolor=brown];
    lc [ label = "C" ];
    ld [ label = "D" ];
    le [ label = "E" xlabel = "ancestor" style=filled, fillcolor=brown];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" style=filled, fillcolor=lightyellow];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

Node A, B, E are node K's ancestors.

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" xlabel="level 1"];
    lb [ label = "B" xlabel = "level 2"];
    lc [ label = "C" ];
    ld [ label = "D" ];
    le [ label = "E" xlabel = "level 3"];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" xlabel = "level 4"];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

The height(depth) of this tree is 4.

Representation of Tree

Parenthetical notation

(A(B(E(K, L), F), C(G), D(H(M), I, J)))

List Representation

digraph foo {
        rankdir=LR;

        node [shape=record];
        a [label="{ <data> A | <ref> }"];
        a1 [label="{ <ref1> | <ref2> }"];
        a2 [label="{ <ref1> | <ref2> }"];
        a3 [label="{ <ref1> | <data> 0}"];
        b [label="{ <data> B | <ref> }"];
        b1 [label="{ <ref1> | <ref2> }"];
        b2 [label="{ <ref1> | <data> 0}"];
        c [label="{ <data> C | <ref> }"];
        c1 [label="{ <data> G | <data> 0 }"];  
        d [label="{ <data> D | <ref> }"];
        d1 [label="{ <ref1> | <ref2> }"];
        d2 [label="{ <data> I | <ref2> }"];
        d3 [label="{ <ref1> | <data> 0}"];
        e [label="{ <data> E | <ref> }"];
        k [label="{ <data> K | <ref> }"];
        l [label="{ <data> L | <ref> }"];
        h [label="{ <data> H | <ref> }"];
        m [label="{ <data> M | <ref> }"];
        
    
        a -> a1;
        a1 -> a2;
        a2 -> a3;
        a2:ref1 -> c:data;
        a1 -> b:data;
        b -> b1;
        b1 -> b2;
        c -> c1:ref1:c1;
        b1:ref1 -> e:data;
        a3:ref1 -> d:data;
        d -> d1;
        d1 -> d2;
        d2 -> d3;
        e -> k:data;
        k -> l:data;
        d1:ref1 -> h:data;
        h -> m:data;
}

Degree K representation

digraph structs {
    node [shape=record];
    struct1 [label="Data|Child 1|Child 2|...|Child k"];
}

Each child field points to a subtree.

e.g. Tree of degree 3

digraph structs {
    node [shape=record];
    A [label="Data|Child 1|Child 2|Child 3"];
}

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "A" ];
    lb [ label = "B" ];
    lc [ label = "C" ];
    ld [ label = "D" ];
    le [ label = "E" ];
    lf [ label = "F" ];
    lg [ label = "G" ];
    lh [ label = "H" ];
    li [ label = "I" ];
    lj [ label = "J" ];
    lk [ label = "K" ];
    ll [ label = "L" ];
    lm [ label = "M" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

Tree of degree 3(13 nodes)

digraph BST {
    node [fontname="Arial" ];
    la  [ label = "3" ];
    lb [ label = "2" ];
    lc [ label = "1" ];
    ld [ label = "3" ];
    le [ label = "2" ];
    lf [ label = "0" ];
    lg [ label = "0" ];
    lh [ label = "1" ];
    li [ label = "0" ];
    lj [ label = "0" ];
    lk [ label = "0" ];
    ll [ label = "0" ];
    lm [ label = "0" ];

    la  -> { lb lc ld};
    lb -> { le lf };
    lc -> { lg };
    ld -> { lh li lj};
    lh -> { lm };
    le -> { lk ll};
}

\(12\) child fields are used

Number of nodes: \(n\)
Degree of tree: \(k\)
Total child fields: \(nk\)

Non-zero child fields: \(n - 1\)

P.S: root node doesn't need to be pointed.

Number of NULL fields

\(nk - (n - 1) = n(k - 1) + 1\)

Verify with our example

\(n(k - 1) + 1 = 13(3 - 1) + 1 = 27\)(unused fields) \(=39 - 12\)(fields in-use)

\((27 / 39)*100 \approx 70\%\) space wasted

Disadvantages:

1. Not efficient with memory usage
2. Need to know the degree of tree before implementation

End