# 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\}$
```graphviz
digraph BST {
node [fontname="Arial" ];
a [label = "A"];
b [label = "B"];
c [label = "C"];
d [label = "D"];
e [label = "E"];
}
```
---
```graphviz
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;
}
```
---
```graphviz
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
---
```graphviz
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.
---
```graphviz
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
---
```graphviz
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};
}
```
---
```graphviz
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.
---
```graphviz
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.
---
```graphviz
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
```graphviz
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
```graphviz
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
```graphviz
digraph structs {
node [shape=record];
A [label="Data|Child 1|Child 2|Child 3"];
}
```
---
```graphviz
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)
---
```graphviz
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
{"metaMigratedAt":"2023-06-17T13:17:16.386Z","metaMigratedFrom":"YAML","title":"11/3 DS Review","breaks":true,"slideOptions":"{\"theme\":\"black\"}","contributors":"[{\"id\":\"8454d940-e0bb-475b-b3fe-eb20c2fe4f94\",\"add\":12371,\"del\":3864}]"}