Comprehensive Guide to Trees and Binary Search Trees in Data Structures

What is a general tree?

A general tree T is a set of one or more nodes partitioned into a root node and disjoint subsets that are general subtrees of the root.

What defines a binary tree?

A binary tree is a set T of nodes that is either empty or partitioned into a root node and two possibly empty binary subtrees.

What are the properties of a binary search tree?

In a binary search tree, a node's value is greater than all values in its left subtree and less than all values in its right subtree.

How is the height of a tree defined?

The height of a tree T is the maximum level of its nodes, with an empty tree having a height of 0.

What is a full binary tree?

A full binary tree is one where every node has either 0 or 2 children.

What is a complete binary tree?

A complete binary tree of height h is full to level h-1 and filled from left to right at level h.

What characterizes a balanced binary tree?

A balanced binary tree is one where the height of any node's left and right subtrees differs by no more than 1.

What is the root of a tree?

The root is the only node in the tree that has no parent.

Define a leaf node.

A leaf node is a node that has no children.

What are siblings in a tree?

Siblings are nodes that share the same parent.

What is the ancestor of a node?

An ancestor of node n is any node on the path from the root to n.

What is a descendant of a node?

A descendant of node n is any node on a path from n to a leaf.

What is a subtree of a node?

A subtree of node n consists of a child of n and that child's descendants.

How is the height of a tree calculated?

The height is calculated as the number of nodes on the longest path from the root to a leaf.

What is an empty binary tree?

An empty binary tree is a binary tree that contains no nodes.

What operations are available for an ADT binary tree?

Basic operations include createBinaryTree(), makeEmpty(), isEmpty(), and getRootItem().

What is preorder traversal?

Preorder traversal visits the root node first, then recursively visits the left subtree followed by the right subtree.

What is inorder traversal?

Inorder traversal visits the left subtree first, then the root node, and finally the right subtree.

What is postorder traversal?

Postorder traversal visits the left subtree first, then the right subtree, and finally the root node.

What is an array-based representation of a binary tree?

An array-based representation uses an array to store tree nodes, where each node contains data and indexes for its children.

What is a reference-based representation of a binary tree?

A reference-based representation uses references to link nodes in the tree.

What is the role of the TreeNode class in a binary tree?

The TreeNode class represents a node in a binary tree.

What is the purpose of the TreeException class?

The TreeException class is used to handle exceptions related to tree operations.

What does the BinaryTree class provide?

The BinaryTree class provides general operations for a binary tree and extends the BinaryTreeBasis class.

What is the significance of the maximum level in a tree?

The maximum level indicates the height of the tree, which is crucial for understanding tree structure and balance.

How do you determine if a binary tree is balanced?

A binary tree is balanced if the heights of the left and right subtrees of any node differ by at most 1.

What does the TreeIterator implement?

The Java Iterator interface.

What is the purpose of the TreeIterator?

To provide methods to set the iterator to the type of traversal desired.

What data structure does the TreeIterator use to maintain the current traversal?

A queue.

What is a key property of a binary search tree?

Each node's value is greater than all values in its left subtree and less than all values in its right subtree.

What is a record in the context of binary search trees?

A group of related items, called fields, that are not necessarily of the same data type.

What is a search key?

The part of a record that identifies it within a collection of records.

What operations can be performed on a binary search tree?

Insert, delete, retrieve, and traverse items.

What does the search algorithm do in a binary search tree?

It searches the binary search tree for the item whose search key is specified.

What are the three possible cases for a node containing an item to be deleted?

1. N is a leaf. 2. N has only one child. 3. N has two children.

What happens if a node N is a leaf during deletion?

Set the reference in N's parent to null.

What is the strategy for deleting a node N with two children?

Locate another node M that is easier to remove, copy M's item to N, and remove node M.

How is the retrieval operation implemented in a binary search tree?

By refining the search algorithm to return the item with the desired search key or a null reference.

What is the theorem regarding inorder traversal of a binary search tree?

It visits the nodes in sorted search-key order.

What does the BinarySearchTree class extend?

It extends BinaryTreeBasis.

What is the maximum number of comparisons for retrieval, insertion, or deletion in a binary search tree?

The height of the tree.

What is the minimum height of a binary tree with n nodes?

⌈log2(n + 1)⌉.

What is Treesort?

An algorithm that uses the ADT binary search tree to sort an array of records into search-key order.

What is the average case efficiency of Treesort?

O(n * log n).

What is the worst-case efficiency of Treesort?

O(n²).

What traversal method is used to save a binary search tree to a file?

Preorder traversal.

What is required to restore a binary tree to a balanced shape?

The data must be sorted, and the number of nodes in the tree must be known.

What are the two binary search methods in JCF?

1. Based on natural ordering. 2. Based on a specified Comparator.

What is the significance of the shape of a binary search tree?

It determines the efficiency of its operations.

How can a binary search tree be restored to its original form?

By performing preorder traversal while saving the tree to a file.

What is the maximum height of a binary search tree with n nodes?

n.

What does the term 'full binary tree' refer to?

A binary tree where every node other than the leaves has two children.

What is the relationship between the height of a binary search tree and the order of operations performed?

The height depends on the order of insertion and deletion operations.