Chapter 39 - Trees
No description yet. This curated deck is ready for daily study.
Card preview (24)
What does a rooted tree have?
» Has a root » Branches » Leaves
What are the differences between a tree in computer science and real life?
» In computer science has its root at the top and its leaves at the bottom
What are the typical uses for rooted trees?
» Manipulating hierarchial data » Manipulated sorted lists of data » Making information easy to search
What is a tree?
» A tree is a fundamental data structure » Consists of nodes and pointers
What does each tree have?
» A root node
What are the leaf nodes?
» Nodes at the very bottom of the tree » And a node which has no children
What are nodes connected with?
» Pointers also known as edges
What is a subtree?
» A set of nodes and edges from any single node down through all of its descendants is known as a subtree
What does each edge connect?
» 2 nodes » Evert node except the root is connect by exactly one edge from another node
What is the root?
» Only root which has no incoming edges
What is the child ?
» The set of nodes that have incoming edges from the same node
What is a binary tree?
» Similar to a standard rooted tree » In which eah node has a maximum of 2 children
What is a binary tree?
» Similar to a standard rooted tree » In which eah node has a maximum of 2 children
How can binary trees be represented in memory?
» As dicitonaries
What are the values of the right pointer/ left pointer if there is no child node?
» Null
What are the applications of binary trees?
» Database applications where efficient searching is required » Wireless networking and routing tables
What does each node in a binary tree contain?
» A left pointer » A right pointer » Data
What are the steps to add an item to a binary tree?
» Check if there is free memory for the node - if there isn’t output an error » Create a new node and insert data into it
What happens if the binary tree is empty when data is being added to it?
» New node becomes first item - create a start pointer to it
What happens if the binary tree is not empty, when trying to add an item to a binary tree?
» Start at root node » If new node should be placed before the current node, follow the left pointer » If new should be placed after the current node, follow the right pointer » Repeat until the leaf node is reached » Set right pointer of the previous node
How can we find the item we want to delete from the binary tree?
» Start at the root node and set it as the current node » While the current node exists and is not the one to be deleted: » If item to be deleted is < than the current node, follow the left pointer, if > follow the right pointer
What are the steps to remove an item from a binary tree if the node has no children?
» If the previous node is greater than the current node, previous node’s left pointer is set to null » Else, the previous node’s right pointer is set to null
What is the Hibbard deletion algorithm?
» To delete a node, we find the smallest value in the right sub-tree(Sucessor) » And move it the position occupied by G » Smalles value in the right - sub tree will always be left-most node in the right sub tree
What are the problems with the Hibbard delete program?
» Tree may become unbalanced, as any node can become the root node.