Chapter 39 - Trees Flashcards by Anonymous T

What does a rooted tree have?

» Has a root
» Branches
» Leaves

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

What are the typical uses for rooted trees?

» Manipulating hierarchial data
» Manipulated sorted lists of data
» Making information easy to search

How well did you know this?

Not at all

Perfectly

What is a tree?

» A tree is a fundamental data structure
» Consists of nodes and pointers

How well did you know this?

Not at all

Perfectly

What does each tree have?

» A root node

How well did you know this?

Not at all

Perfectly

What are the leaf nodes?

» Nodes at the very bottom of the tree
» And a node which has no children

How well did you know this?

Not at all

Perfectly

What are nodes connected with?

» Pointers also known as edges

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

What does each edge connect?

» 2 nodes
» Evert node except the root is connect by exactly one edge from another node

How well did you know this?

Not at all

Perfectly

What is the root?

» Only root which has no incoming edges

How well did you know this?

Not at all

Perfectly

What is the child ?

» The set of nodes that have incoming edges from the same node

How well did you know this?

Not at all

Perfectly

What is a binary tree?

» Similar to a standard rooted tree
» In which eah node has a maximum of 2 children

How well did you know this?

Not at all

Perfectly

What is a binary tree?

» Similar to a standard rooted tree
» In which eah node has a maximum of 2 children

How well did you know this?

Not at all

Perfectly

How can binary trees be represented in memory?

» As dicitonaries

How well did you know this?

Not at all

Perfectly

What are the values of the right pointer/ left pointer if there is no child node?

» Null

How well did you know this?

Not at all

Perfectly

What are the applications of binary trees?

» Database applications where efficient searching is required
» Wireless networking and routing tables

How well did you know this?

Not at all

Perfectly

What does each node in a binary tree contain?

» A left pointer
» A right pointer
» Data

How well did you know this?

Not at all

Perfectly

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

How well did you know this?

Not at all

Perfectly

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