Introducing
Prezi AI.
Your new presentation assistant.
Refine, enhance, and tailor your content, source relevant images, and edit visuals quicker than ever before.
Trending searches
Loading…
Binary Trees - Algorithm Design
6
Transcript
Martín Ángel Martín Caño
2022/23
Binary Trees
Algorithm Design
Table of contents
- What is a tree?___________________4
- What is a binary tree? _______7
- Binary Tree Traversa___________10
- Depth-first order____________ 11
- Preorder ________________ 12
- Inorder __________________ 14
- Postorder _______________ 16
- Breadth-first order _________ 19
- Binary Expression Tree ________22
- Binary Search Tree_____________24
- Search______________________ 25
- Insertion____________________ 27
- Deletion_____________________29
What is a tree?
- Nodes connected to an upper node are called “children” of that upper node, which if called “parent”.
- The number of children of a node determines its “degree”.
- “Leaf” nodes are those which don’t have any child.
- 3 operations: search, insertion, deletion
- It’s an abstract data structure.
- Data is stored in “nodes”.
- The topmost node is called the “root” node.
- Nodes are connected with lines, called “branches”.
Definition
Binary tree
- Data structure in which each node only has two children (left and right).
What is a binary tree?
Binary Tree Traversal
Traversal
- Each node has to be visited only once, in a specific sequence.
- Two main focuses for the traversal sequence:
- Depth-first order
- Breadth-first order
Depth-first order
- This process requires a path from the root through a child, to the most distant descendant of the first child before continuing with a second child.
- This is, all the descendants of a child are processed before the next child.
Depth-first order
- Given a binary tree consisting of root, left and right subtree, we define three kinds of sequence for the depth-first traversal:
Preorder
- The root node gets visited first, followed by the left subtree and finally the right subtree.
Preorder
Inorder
- Nodes from the left subtree are visited first, followed by the root node and finally the right subtree
Inorder
Postorder
- Nodes from the left subtree get visited first, followed by the right subtree, and finally the root.
Postorder
Breadth-first order
- The process is made horizontally, from the root node to all its children, then to their children’s children and so on until every node has been visited.
- In resume, every single level is visited completely before continuing with the next one.
Breadth-first order
Binary Expression Tree
- Used to represent expressions
- Each leaf node represents an operand
- Root node and intern nodes represent operators
- Subtrees are subexpressions whose root is an operator
- Traversal: generally inorder
Binary Expression Tree
Binary Search Tree (BST)
- Given a specific node, all data in the left subtree is less than the data in the right subtree -> Left child < Right child, for every node
- Needs values that can be compared with “<”, “<=”, “>” or “>=” operator
- Operations:
- Search
- Insertion
- Deletion
Binary Search Tree
Search
- Searching in a binary search tree for a specific key can be programmed recursively or iteratively.
- Firstly, the root node is examined. If the key is equal to the root, the search is successfull and the node is returned.
- If the key is less than that of the root, the search proceeds examining the left subtree, whilst if the key is greater than that of the root, the search proceeds examining the right subtree.
- The process is repeated until the key is found or the whole tree has been examined, that is, the key is not present in the tree.
Insertion
- Similarly to the search operation, the insertion of a new node depends on its key.
- If the key is smaller than that on the root node, the left node is examined, if there is no left child, the node is inserted in that position, whereas if there is, the process must continue.
- The process is similar when the key is greater that that on the root node: if there is no right child, the node is inserted there, if there is, its key is examined.
- The process continues until a place is found.
Insertion
Deletion
- n is simply removed from the tree (its parent pointer gets replaced with a null value and n is removed)
- The child becomes the new left or right child of n's parent node, depending on the position of n.
Deletion
- There are 3 cases:
- The node to be deleted (n) is a leaf node.
- The node (n) has one child.
- The node (n) has both left and right child.
- We search for the node from the right subtree which has the smallest key. That node will replace n.
Bibliography
- https://www.geeksforgeeks.org/introduction-to-tree-data-structure-and-algorithm-tutorials/
- https://www.cs.cmu.edu/~clo/www/CMU/DataStructures/Lessons/lesson4_1.htm
- http://cslibrary.stanford.edu/110/BinaryTrees.html
- Estructura de datos en C++ - McGrawHill (Luis Joyanes & Ignacio Zahonero)
Thank you for your attention!
The end
Choose a template
Presentations from around the world
Learn more about creating dynamic, engaging presentations with Prezi