Types of Binary Trees
Trees are a fundamental data structure with applications in various domains like family relationships, organizational hierarchies, and file systems. This theoretical exploration delves into the terminology and types of binary trees, including complete, full, nearly complete, and binary trees used in recursive functions. Learn about tree properties like root, path, internal nodes, leaves, subtree, and more. Enhance your knowledge of tree structures and their practical significance in algorithm analysis.
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.
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
Trees (Part 1, Theoretical) CSE 3318 Algorithms and Data Structures University of Texas at Arlington 2/22/2025 1
Trees Trees are a natural data structure for representing specific data. Family trees. Organizational chart of a corporation, showing who supervises who. Folder (directory) structure on a hard drive. Theoretical usage analysis of recursive functions with 2 or more recursive calls 2
Terminology Root: 0 (has no parent) Path: 0-2-6, 1-3, 1-3-4 Parent vs child Ascendants vs descendants: ascendants of 3: 1, 0 descendants of 1: 5, 3, 4, 8 Internal nodes: 0, 1, 2, 3 Have 1 or more children Leaves: 5,4,6,7,8 Have no children Subtree 0 1 2 6 7 5 3 4 8 3
Terminology - Worksheet The level of the root is defined to be 0. The level of each node is defined to be 1+ the level of its parent. Thedepthof a node is the number of edges from the root to the node. (It is equal to the level of that node.) The height of a node is the number of edges from the node to the deepest leaf. (Treat that node as the root of a small tree) A Node level depth height A B B C C Practice: - Give the level, depth and height for each of the red nodes. - How many nodes are on each level? __________________________________ 4
Terminology - Answers The level of the root is defined to be 0. The level of each node is defined to be 1+ the level of its parent. Thedepthof a node is the number of edges from the root to the node. (It is equal to the level of that node.) The height of a node is the number of edges from the node to the deepest leaf. (Treat that node as the root of a small tree) level 0 A Node level depth height A 0 0 3 1 B 2 2 1 B C 3 3 0 2 3 C Practice: - Give the level, depth and height for each of the red nodes. - How many nodes are on each level? ________1, 2, 4, 8 __________________ 5
Types of binary trees Complete (or perfect) each internal node has exactly 2 children and all the leaves are on the same level. E.g. ancestry tree (anyone will have exactly 2 parents). Full [binary] every node has exactly 0 or 2 children. Tree of recursive calls when there are 2 recursive calls E.g. tree generated by the Fibonacci recursive calls. => his properties are used in analyzing time complexity of such rec fcts. Binary tree. Nearly complete tree every level, except for possibly the last one is completely filled and on the last level, all the nodes are as far on the left as possible. E.g. the heap tree. Height: and it can be stored as an array. N lg Complete tree Nearly Complete tree 6
Complete Binary Trees A complete binary tree with N nodes and height h, has: leaves (half the nodes are on the last level) internal nodes (half the nodes are internal) Height : Levels : (= lg(N+1) ) 1 lg + N 2 / 2 / N N 2?= 2 +1 1 ?=0 = lg h N Level Nodes per level Sum of nodes from root up to this level In the other direction: N = 2h+1 -1 20 (=1) 21 1 (=1) 0 1 21 (=2) 22 1 (=3) 1 22 (=4) 23 1 (=7) 2 2 3 4 6 5 7 2i 2i+1 1 i . . . . . . . . . . . . . . . . . . . . . 2h-1 2h-1 h-1 . . . 7 2h 2h+1 1 h
Nearly Complete Tree All levels are full, except possibly for the last level. At the last level: Nodes are on the left. Empty positions are on the right. There is no hole Good 9 1 Bad 7 2 5 3 Bad Bad 3 4 5 5 4 6 3 7 2 8 1 9 1 10 3 11 4 12 1 13 8
Worksheet Self study: Give examples of trees that are: Complete Full but not nearly complete Nearly complete but not full Neither full not nearly complete 9
E1 9 Worksheet 7 5 For each tree, say if it is full, nearly complete or complete. 3 5 5 5 2 4 1 3 5 5 5 5 E2 E3 9 9 7 5 7 5 3 5 5 5 3 5 5 5 5 5 1 3 5 1 3 5 5 5 5 E4 E5 9 9 7 5 8 4 3 5 5 7 5 1 4 2 1 1 3 5 5 3 6 2 1 0 4 0 10
E1 9 Answers For each tree, say if it is perfect, nearly complete or complete. E2 Complete 7 5 3 5 5 5 2 4 1 3 5 5 5 5 E3 9 9 Nearly complete, not full Full, not nearly complete 7 5 7 5 3 5 5 5 3 5 5 5 5 5 1 3 5 1 3 5 5 5 5 E4 E5 9 9 Neither full, nor nearly complete Neither full, nor nearly complete 7 5 8 4 3 5 5 7 5 1 4 2 1 1 3 5 5 3 6 2 1 0 4 0 11
Properties of Full Trees Full binary tree : every node has exactly 0 or 2 children. No nodes with only 1 child. A full binary tree with X internal nodes has: X+1 external nodes. 2X edges (links). N = 2X+1 (total number of nodes) height at least lg X and at most X: Height O(lgX) if all external nodes are at the same level (complete tree) Height O(X) if each internal node has one external child 12
Proof Prove that a full tree with P internal nodes has P+1 external leaves. Full tree property: What proof style will you use? 13
Proof Prove that a full tree with P internal nodes has P+1 external leaves. Full tree property: What proof style will you use? 14
