Chapter 39 - Trees Flashcards
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.
What are the problems of adding and deleting nodes?
» It can impact the efficiency algorithms on binary trees
What are the steps to use hibbard deletion if the right node exists and it has no left sub tree?
» Set the current node to the node’s right pointer
» Set the current node’s pointer to null
What is a simple alternative to delete nodes from a tree?
» Is to introduce another attribute to each node that flags it for delted
» These deleted nodes are skipped when traversing the tree
What is a simple alternative to delete nodes from a tree?
» Is to introduce another attribute to each node that flags it for delted
» These deleted nodes are skipped when traversing the tree
What is the problem of flagging?
» Increase space complexity
What are the three different binary tree traversal methods that you need to be aware of?
» Pre-order
» In-order
» Post-order
What is pre-order traversal?
» A variation of a depth-first search used to create a copy of a binary tree
What are the steps of pre-order traversal?
» Start at root node
» Output node
» Traverse the left sub tree - Continue traversing through the left pointer, until there is no pointer to traverse
» Return to previously visted node and traverse the right sub-tree
» Returen the root node and traverse the right sub-tree
What is in-order traversal?
» Variation of depth-first search to output the contents
What is the signifcant advantage of in-order traversal?
» Automatically sorts the contents of the structure without moving data - negates the need for insertion sort
What are the steps of in-order traversal?
» Traverse the left-sub tree
» Go as fat as possible along the left-sub tree
» Return from the point visting the other nodes
» Traverse as far as possible on the right-sub tree
» Return to the root visiting the root node
How can you output nodes in reverse order?
» Simply reverse the algorithm by following the right pointer before outputting the node
What is a good exam tip?
» Make sure you read the question carefully to check whether it ask for a right hand tree or a left hand treee
What is prefix notation?
» Polish notation - Pre-order traversal
What is infix notation?
» Inorder traversal
What is postfix notation?
» Post order traversal
» Reverse polish notation
What is post-order traversal?
Depth-first search to delete a binary tree
What are the steps of a post-order traversal?
» Start at the root node
» Traverse left sub-tree
» Follow the left pointer until it is far down as possible
» Go as far as down on the left sub tree
» Return to root visiting node
» Traverse right sub-tree
What is one key tip to remember in post-order traversal?
» Each markers are on the right hand side of each node
What is the purpose of Reverse polish notation?
» To evaluate algebraic expressions
What are the steps to add nodes to a binary tree?
» Start at root node
» If item is less, go left
» If item is more go right
What is tree traversal?
» The process of visiting(checking or updating) each node in a tree data structure
What are the benfits of a binary tree?
» Dynamic
» Printed out in a sequence
» Searched quickly
