BINARY TREES

Slide Note

This content covers the concepts of binary trees, tree structures, and terminology related to trees in computer science. It includes detailed explanations, examples, and images to aid in understanding the topic. Topics discussed range from binary tree structures to node relationships, siblings, subtrees, and leaf nodes. Explore the world of trees in data structures and algorithms through this comprehensive guide.

jahlayah Follow

Uploaded on Feb 22, 2025 | 0 Views

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.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download 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.

E N D

Presentation Transcript

BINARY TREES David Kauchak CS 62 Spring 2021

Admin Learning community reorganization https://docs.google.com/spreadsheets/d/1xvZL4y_FTq1h8nhYFmwCYBL_qv2 neLM-n8KqkNRdadA/edit#gid=0 Advisor declaration + pre-pre enrollment Town hall this afternoon (4:10pm) Office hours today: 3:30-4pm

Trees 2 14 10 root 3 1 9 7 leaves 16 2 8 4

Trees A set of nodes based on a parent-child relationship 2 Each node has one parent 14 10 Root has no parent 3 1 9 7 16 2 8 4

Another example B F C A D E

Another example: the lone wolf 12

Another example: the twig D B A F

Binary tree 2 14 10 Each parent has at most 2 children 3 1 9 7 16 2 8

Tree terminology Edge: - one of the lines - Defined by a parent and child, (C,F) F C A G H B E E E F

Tree terminology F Sibling: two nodes that share the same parent C A E and F are siblings G H B E E E F

Tree terminology F Subtree: a node and all of the nodes below it C A subtree rooted at C G H B E E E F

Tree terminology F Leaf: node without any children Internal node: non-leaf node C A G H B E E E F

Tree terminology F Simple path: a series of distinct nodes with edges between successive nodes C A F-C-H-E G H B E E E F

Tree terminology F Simple path: a series of distinct nodes with edges between successive nodes C A F-C-H-E G H B E Path length: number of edges on path E E F How long is this path?

Tree terminology F Simple path: a series of distinct nodes with edges between successive nodes C A F-C-H-E G H B E Path length: number of edges on path E E F 3, (F,C), (C,H), (H,E)

Tree terminology F Height of a node: length of longest path from the node to a leaf C A G H B E What is the height of C? E E F

Tree terminology F Height of a node: length of longest path from the node to a leaf C A G H B E What is the height of C? E E F 2

Tree terminology F Height of a node: length of longest path from the node to a leaf C A G H B E What is the height of C? E F

Tree terminology F Height of a node: length of longest path from the node to a leaf C A G H B E What is the height of C? E F 2

Tree terminology F Height of the tree: height of the root (longest path from root to a leaf) C A G H B E What is the height of the tree? E E F

Tree terminology F Height of the tree: height of the root (longest path from root to a leaf) C A G H B E What is the height of the tree? E E F 3

Tree terminology D What is the height of the tree? B A F

Tree terminology D What is the height of the tree? B 3 A F

Tree terminology F Degree of node: number of children C A Degree of tree (arity): max degree of any of the nodes G H B E What is the degree of the tree? E E F

Tree terminology F Degree of node: number of children C A Degree of tree (arity): max degree of any of the nodes G H B E What is the degree of the tree? 2 E E F

Tree terminology 2 Degree of node: number of children 14 10 Degree of tree (arity): max degree of any of the nodes 3 1 9 7 What is the degree of the tree? 16 2 8 4

Tree terminology 2 Degree of node: number of children 14 10 Degree of tree (arity): max degree of any of the nodes 3 1 9 7 What is the degree of the tree? 3 16 2 8 4

Tree terminology F Level/depth of node: - Root is 0 - Level(child) = 1 + level(parent) C A (also: length of path from root to node) G H B E What is the depth of G? E E F

Tree terminology F Level/depth of node: - Root is 0 - Level(child) = 1 + level(parent) C A (also: length of path from root to node) G H B E What is the depth of G? E E F 2

Tree terminology F Height of node: - Leaf is 0 - h(node) = max height of children C A G H B E What is the height of C? E F

Tree terminology F Height of node: - Leaf is 0 - h(node) = max height of children C A G H B E What is the height of C? E F 2

Tree terminology (almost there!) Full tree: a binary tree where every node has 0 or 2 children Complete: All levels except the last are completely filled and all nodes on the last level are on the left

Full + Complete

Full + Complete? 12 Full tree: a binary tree where every node has 0 or 2 children Complete: All levels except the last are completely filled and all nodes on the last level are on the left

Full + Complete? 12 Complete Neither Full + Complete

Nodes in a binary tree F What is the most nodes we can have at a level k? C A Level = 2 G H B E E F

Nodes in a binary tree F What is the most nodes we can have at a level k? C A Level = 2 G H B E At most 2k nodes (when every node above it has two children) E F

Nodes in a binary tree F What is the most nodes we can have in a tree of height h? C A G H B E E F

Nodes in a binary tree F What is the most nodes we can have in a tree of height h? C A G H B E 1 + 2 + 4 + 8 + + 2 = 2 +1 1 When the tree is full and complete!