Ch 4: Trees Flashcards
what is a binary tree?
a tree where each node has up to two “children”: left and right child
what is a leaf?
a tree node with no children
what is an internal node?
a node with at least one child
what is the parent?
a node with a child is said to be the child’s parent
what are ancestors?
the node’s parent, the parent’s parent, etc. up to the tree’s root
what is a root node?
the one tree node with no parent (“top” node)
what is an edge?
a link from a node to a child
what is a node’s depth?
number of edges on the path from the root to the node
what is a tree’s height?
the largest depth of any node
what is the height of a tree with no nodes?
height is 0
when is a tree full?
every node contains 0 or 2 children
when is a tree complete?
when all levels, except possibly the last level, contain all possible nodes and all nodes in the last level are as far left as possible
when is a tree perfect?
when all internal nodes have 2 children and all leaf nodes are at the same level
what are trees commonly used to represent?
hierarchical data
what is binary space partitioning (BSP)?
a technique of repeatedly separating a region of space into two parts and cataloging objects contained within the regions
what is a BSP tree?
a binary tree used to store information for BSP
what is in each node of a BSP tree?
holds information about a region of space and which objects are contained in this region
what is a binary search tree (BST)?
- a form of a binary tree that has an ordering property that any node’s left subtree keys are less than the nodes keys and the right subtree keys are more than the nodes keys
- ordering property allows for faster searching
what is search?
to find a node with a desired key, if such node exists
what is a successor?
the node that comes after in the BST ordering
what is a predecessor?
the node that comes before in the BST ordering
what is the search algorithm?
given a key, returns first node found watching key or null if matching node with found
what is insert?
an operation that inserts a new node in a proper location obeying the BST ordering property
what is remove?
an operation that removes the first-found matching node, restructuring the tree to preserve the BST ordering property
what is tree traversal?
an algorithm that visits all nodes in the tree once and performs an operation on each node
what is in-order traversal?
visits all nodes in a BST from smallest to largest
what is in-order traversal useful for?
when printing tree’s nodes in sorted order
what is a trie (prefix tree)?
a tree representing a set of strings
what does each node represent in a trie?
represents a single character and has at most one child per distinct alphabet character
what is a terminal node?
represents a terminating character, which is the end of a string in the trie
what is trie insert
an operation that creates a path from the next to a terminal node that visits all the string’s characters in a sequence
explain the trie insert algorithm
a current node pointer initially points to root node, then a loop iterates through the string’s characters. for each character C, a new child node is added only if the current node does not have a child for C. the current node pointer is assigned with the current node’s child for C. after all characters are processed, a terminal node is added and returned
what is trie search?
an operation that returns the terminal node corresponding to that string, or null if the string is not in the trie
what is trie remove?
an operation that removes the string’s corresponding terminal code and non-root ancestors with 0 children
explain BST insert algorithm
- if root is null then node is set to root
- if root isn’t null, then if key is less than root it’ll check if root’s left is empty. if it is then node is placed. other wise it’ll check again if key is greater than or less than the node and keep traversing until it finds it spot
- if root isn’t null and key is more than root it’ll check Iif roots right is empty. if it is then node is placed otherwise it’ll check again if key is greater than or less than the node and keep traversing until it finds it spot
explain BST remove algorithm
- search for a matching node in the tree
- if found:
- if node is a leaf node, the node is removed and parents left/right is set to null, if node was root then root is set to null and tree is empty
- if node is an internal node with one child, then the parent node’s child will be set to the current node’s child
- if node is an internal node with two children, the successor is found (the right most child in node’s subtree) and copied in place of the current node. the originally successor is deleted
explain BST inorder traversal algorithm
- current node points to root
- if root is null, return otherwise printInOrder is recursively called on root’s left, then current node is printed, then printInOrder is recursively called on root’s right
