- Why Use Binary Trees?
- Tree Terminology
- An Analogy
- How Do Binary Search Trees Work?
- Finding a Node
- Inserting a Node
- Traversing the Tree
- Finding Minimum and Maximum Key Values
- Deleting a Node
- The Efficiency of Binary Search Trees
- Trees Represented as Arrays
- Printing Trees
- Duplicate Keys
- The BinarySearchTreeTester.py Program
- The Huffman Code
- Summary
- Questions
- Experiments
- Programming Projects
This chapter is from the book
This chapter is from the book
This chapter is from the book
Questions
These questions are intended as a self-test for readers. Answers may be found in Appendix C.
Insertion and deletion in a binary search tree require what Big O time?
A binary tree is a search tree if
every nonleaf node has children whose key values are less than or equal to the parent.
the key values of every nonleaf node are the sum or concatenation of the keys of its children
every left child has a key less than its parent and every right child has a key greater than or equal to its parent.
in the path from the root to every leaf node, the key of each node is greater than or equal to the key of its parent.
True or False: If you traverse a tree and print the path to each node as a series of the letters L and R for whether the path followed the left or right child at each step, there could be some duplicate paths.
When compared to storing data in an ordered array, the main benefit of storing it in a binary search tree is
having the same search time as traversal time in Big O notation.
not having to copy data when inserting or deleting items.
being able to search for an item in O(log N) time.
having a key that is separate from the value identified by the key.
In a complete, balanced binary tree with 20 nodes, and the root considered to be at level 0, how many nodes are there at level 4?
A subtree of a binary tree always has
a root that is a child of the main tree’s root.
a root unconnected to the main tree’s root.
fewer nodes than the main tree.
a sibling with an equal or larger number of nodes.
When implementing trees as objects, the ______ and the _______ are generally separate classes.
Finding a node in a binary search tree involves going from node to node, asking
how big the node’s key is in relation to the search key.
how big the node’s key is compared to its right or left child’s key.
what leaf node you want to reach.
whether the level you are on is above or below the search key.
An unbalanced tree is one
in which most of the keys have values greater than the average.
where there are more nodes above the central node than below.
where the leaf nodes appear much more frequently as the left child of their parents than as the right child, or vice versa.
in which the root or some other node has many more left descendants than right descendants, or vice versa.
True or False: A hierarchical file system is essentially a binary search tree, although it can be unbalanced.
Inserting a node starts with the same steps as _______ a node.
Traversing tree data structures
requires multiple methods to handle the different traversal orders.
can be implemented using recursive functions or generators.
is much faster than traversing array data structures.
is a way to make soft deletion of items practical.
When a tree is extremely unbalanced, it begins to behave like the ______ data structure.
Suppose a node A has a successor node S in a binary search tree with no duplicate keys. Then S must have a key that is larger than _____ but smaller than or equal to _______.
Deleting nodes in a binary search tree is complex because
copying subtrees below the successor requires another traversal.
finding the successor is difficult to do, especially when the tree is unbalanced.
the tree can split into multiple trees, a forest, if it’s not done properly.
the operation is very different for the different number of child nodes of the node to be deleted, 0, 1, or 2.
In a binary tree used to represent a mathematical expression,
both children of an operator node must be operands.
following a post-order traversal, parentheses must be added.
following a pre-order traversal, parentheses must be added.
in pre-order traversal, a node is visited before either of its children.
When a tree is represented by an array, the right child of a node at index n has an index of _______.
True or False: Deleting a node with one child from a binary search tree involves finding that node’s successor.
A Huffman tree is typically used to _______ text data.
Which of the following is not true about a Huffman tree?
The most frequently used characters always appear near the top of the tree.
Normally, decoding a message involves repeatedly following a path from the root to a leaf.
In coding a character, you typically start at a leaf and work upward.
The tree can be generated by removal and insertion operations on a priority queue of small trees.