Java Software Structures Chapter 11

A binary search tree is a binary tree with the added property that the left child is less than the parent, which is less than or equal to the right child.

The definition of a binary search tree is an extension of the definition of a binary tree.

Each BinaryTreeNode object maintains a reference to the element stored at that node, as well as references to each of the node's children.

<p>In removing an element from a binary search tree, another node must be promoted to replace the node being removed.</p> Signup and view all the answers

<p>The leftmost node in a binary search tree will contain the minimum element, whereas the rightmost node will contain the maximum element.</p> Signup and view all the answers

<p>One of the uses of trees is to provide efficient implementations of other collections.</p> Signup and view all the answers

<p>If a binary search tree is not balanced, it may be less efficient than a linear structure.</p> Signup and view all the answers

<p>The height of the right subtree minus the height of the left subtree is called the balance factor of a node.</p> Signup and view all the answers

<p>There are only two ways in which a tree, or any subtree of a tree, can become unbalanced: through the insertion of a node and through the deletion of a node.</p> Signup and view all the answers

<p>False</p> Signup and view all the answers

<p>A binary tree with an added ordering property</p> Signup and view all the answers

<p>Promoted</p> Signup and view all the answers

<p>A degenerate tree is a tree that does not branch.</p> Signup and view all the answers

<p>A single rotation strategy for rebalancing a tree when the long path is in the left subtree of the left child of the root.</p> Signup and view all the answers

<p>A single rotation strategy for rebalancing a tree when the long path is in the right subtree of the right child of the root.</p> Signup and view all the answers

<p>A double rotation strategy for rebalancing a tree when the long path is in the left subtree of the right child of the root.</p> Signup and view all the answers

<p>A double rotation strategy for rebalancing a tree when the long path is in the right subtree of the left child of the root.</p> Signup and view all the answers

<p>A strategy for keeping a binary search tree balanced that makes use of the balance factor of each node.</p> Signup and view all the answers

<p>A property of a node that is computed by subtracting the height of the left subtree from the height of the right subtree.</p> Signup and view all the answers

<p>A strategy for keeping a binary search tree balanced that makes use of a color (either red or black) associated with each node.</p> Signup and view all the answers

<p>A binary search tree has the added ordering property that the left child of any node is less than the node, and the node is less than or equal to its right child.</p> Signup and view all the answers

<p>With the added ordering property of a binary search tree, we are now able to define what the state of the tree should look like after these operations.</p> Signup and view all the answers