Trees: Introduction and Definitions
undefined
Trees: Intro and
Trees: Intro and
Definitions
Definitions
Moving on from Lists
Moving on from Lists
Lists: the good, the bad!
Lists:
Same type, ordered, allows duplicates, has a size
Good:
Arrays: find the kth value in O(1)!
Linked Lists: push, pop, join in O(1)
Bad:
Finding if k is in the list.
Regardless of implementation, this will, in the worst case, require TRAVERSING THE
ENTIRE LIST (weep, moan, groan in agony!) This is O(n) (ugh, blech!)
Tree (new ADT)
3
Terminology:
tree
=collection of elements (nodes)
Each node may have
0 or more
successors
(called
children)
How many does a list have?
Each node has
exactly one
predecessor
(called the
parent
)
Except the starting node, called the
root
Branches
Links from node to its successors
Siblings
Nodes with same parent
leaves
Nodes with no children are called
Tree
We also use words like
ancestor
and
descendent
4
•
P
e
t
s
i
s
t
h
e
p
a
r
e
n
t
o
f
D
o
g
s
,
C
a
t
s
a
n
d
R
a
b
b
i
t
s
•
P
o
o
d
l
e
,
B
e
a
g
l
e
a
n
d
C
o
r
g
i
a
r
e
t
h
e
c
h
i
l
d
r
e
n
o
f
D
o
g
s
•
P
o
o
d
l
e
,
B
e
a
g
l
e
,
C
o
r
g
i
,
P
e
r
s
i
a
n
,
S
i
a
m
e
s
e
,
M
i
n
i
L
o
p
,
a
n
d
R
e
x
a
r
e
d
e
s
c
e
n
d
e
n
t
s
o
f
P
e
t
s
,
•
P
e
t
s
i
s
t
h
e
a
n
c
e
s
t
o
r
o
f
C
o
r
g
i
,
P
o
o
d
l
e
,
B
e
a
g
l
e
,
P
e
r
s
i
a
n
,
S
i
a
m
e
s
e
,
M
i
n
i
L
o
p
a
n
d
R
e
x
Rabbits
Corgi
Mini Lop
Rex
Tree Terminology
Subtree
of a node:
A tree whose root is a child of that node
Green, blue, and red are all subtrees of tree
with 7 as root!
5
Depth
Binary Trees
Subset of trees
Binary tree: a node has
at most
2
nonempty subtrees
Set of nodes T is a binary tree if either of these is true:
T is empty
Root of T has two subtrees, both binary trees
(Notice that this is a
recursive
definition)
6
This is a
binary
tree
class TNode {string data;
TNode *left;
TNode *right;
TNode *parent;
};
Trees grow from the
top down
New values inserted in new leaf nodes
In a
full tree
, every node has 0 or 2 non-null children
A
complete tree
of height
h
is filled up to depth
h
-1, and, at depth
h
, any unfilled nodes
are on the right.
7
Fullness and Completeness (for binary tree):
Takeaways:
Tree: New ADT
Each node in a tree has:
only one parent
Root: no parent – starting point in trees
0 or more children
Height of a node:
Take the height of each of a node’s children , find the max, and add 1
Leaves have a height of 1
Binary tree – subset of trees
In this case every node has 0, 1, or 2 children
No more than 2!
Full tree – each node has 0 or 2 children (no node with 1 child)
Complete tree – each LEVEL has all possible siblings
Except bottom level (leaf level) which has all possible siblings from the
left over to the right.
Moving on from lists, trees represent a collection of elements where each node may have zero or more successors, known as children. The tree structure includes terminology such as branches, siblings, leaves, ancestors, and descendants. Nodes in a tree have attributes like depth and height, with binary trees being a subset that involves nodes with at most two nonempty subtrees.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Trees: Intro and Definitions Moving on from Lists
Lists: the good, the bad! Lists: Same type, ordered, allows duplicates, has a size Good: Arrays: find the kth value in O(1)! Linked Lists: push, pop, join in O(1) Bad: Finding if k is in the list. Regardless of implementation, this will, in the worst case, require TRAVERSING THE ENTIRE LIST (weep, moan, groan in agony!) This is O(n) (ugh, blech!)
Tree (new ADT) Terminology: tree =collection of elements (nodes) Each node may have 0 or more successors (called children) How many does a list have? Each node has exactly onepredecessor (called the parent) Except the starting node, called the root Branches Links from node to its successors Siblings Nodes with same parent leaves Nodes with no children are called 3
Tree We also use words like ancestor and descendent Rabbits Rex Mini Lop Corgi Pets is the parent of Dogs,Cats and Rabbits Poodle, Beagle and Corgi are the children of Dogs Poodle, Beagle, Corgi,Persian, Siamese, Mini Lop, and Rex are descendents of Pets, Pets is the ancestor of Corgi,Poodle, Beagle, Persian, Siamese, Mini Lop and Rex 4
Tree Terminology Depth of a node: A measure of its distance from the root: Depth of the root = 0 Depth of other nodes = 1 + depth of parent (recursive def!!!) Height of a node: Subtree of a node: A tree whose root is a child of that node Green, blue, and red are all subtrees of tree with 7 as root! Depth The node s maximum distance from its leaf Calculate: find the height of each child, whichever has the larger height, add 1 to that So: Max height of a node s children + 1 e.g., height of 6 is 1, height of 3 is 3, height of 1 is 4 (Again, recursive definition!!! Starting to see a theme???) We will be more concerned with height! 1 2 3 4 5
Binary Trees Subset of trees Binary tree: a node has at most 2 nonempty subtrees Set of nodes T is a binary tree if either of these is true: T is empty Root of T has two subtrees, both binary trees (Notice that this is a recursive definition) class TNode { }; This is a binary tree string data; TNode *left; TNode *right; TNode *parent; 6
Fullness and Completeness (for binary tree): Trees grow from the top down New values inserted in new leaf nodes In a full tree, every node has 0 or 2 non-null children A complete tree of height h is filled up to depth h-1, and, at depth h, any unfilled nodes are on the right. 7
Takeaways: Tree: New ADT Each node in a tree has: only one parent Root: no parent starting point in trees 0 or more children Height of a node: Take the height of each of a node s children , find the max, and add 1 Leaves have a height of 1 Binary tree subset of trees In this case every node has 0, 1, or 2 children No more than 2! Full tree each node has 0 or 2 children (no node with 1 child) Complete tree each LEVEL has all possible siblings Except bottom level (leaf level) which has all possible siblings from the left over to the right.
