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