64 Questions
In a binary sorted tree, what type of elements does the left subtree of a node contain?
Elements less than or equals to the node element
When searching for a target element in a binary sorted tree, if the target is less than or equals to the node element, where should the search go?
Down the left subtree
What does the BSTree Java class constructor with no parameters do?
Constructs an empty binary sorted tree
What does the BSTreeNode Java class represent?
Nodes in a binary sorted tree
What defines a balanced binary tree?
The height difference between the left and right subtrees of every node is at most 1
How is the maximum number of nodes for a binary tree of height 1 determined?
3
What characterizes a proper binary tree?
Each node has either 0 or 2 children
What is the height of a balanced binary tree of size n?
$\lfloor \log_2 n \rfloor + 1$
In heap insertion, when adding a new node to the lowest point in the tree, what is the next step after placing the new node?
Upheap node values to its rightful place in the tree
In heap deletion, what is the condition for swapping a child node with the new node in a max heap?
If child node is greater than the new node
What type of deletion is allowed in a heap data structure?
Restricted deletion called extraction
What is the time complexity of a well-balanced tree for insertion and deletion operations?
O(log n)
How does each insertion and deletion operation affect the balance of a tree?
They affect the balance of the tree
What is the objective in maintaining the balance of a tree after each operation?
To keep the height of the tree to a minimum
What does the balance of a node in a tree represent?
The height of the right sub-tree minus the height of the left sub-tree
How is the balance of a node calculated in a tree?
Balance(n) = right-height(n) - left-height(n)
In a balanced binary tree, what is the relationship between the heights of the left and right sub-trees of a node?
The heights are such that the absolute difference is at most 1
What is the maximum number of nodes and elements on level 3 of a B-Tree of order 100?
Nodes: 202, Elements: 40,401
What variant of B-Tree facilitates sequential access of a file by having pointers in leaf nodes to the next sibling?
B+Tree
What percentage of fullness do B*Trees operate at on average?
81%
In a B-Tree of order 2, what is the resulting tree after adding the sequence: 80, 20, 60, 40, 30, 90, 35, 50, 10, 15, 31, 5, 23, 18, 22, 12, 95?
The resulting B-Tree after adding the given sequence
When does a node in a B-tree need to split into 2 nodes?
When it has more than 2n elements
What happens when a node in a B-tree becomes full?
It must split into 2 nodes
What happens when a new element needs to be added to a full B-tree with a full root node?
The root node is split and a new root node is created
What is the objective in maintaining the balance of a binary tree?
To optimize search and insertion operations
What is the purpose of B-trees in the context of hierarchical abstract data types?
Efficiently handle large amounts of data and minimize disk access
When discussing hierarchical abstract data types, what does a balanced binary tree aim to achieve?
Minimize the height disparity between left and right subtrees
How is the size of a tree defined?
The total number of nodes
What is a characteristic of a node in a tree?
A node must have only one unique path from the root
What does the height of a tree represent?
The number of levels with nodes
What forms the left and right subtrees in a binary tree?
Left child and its descendants for the left subtree, right child and its descendants for the right subtree
What is the maximum number of children a node can have in a binary tree?
2
What characterizes a complete binary tree of height h?
It is full to level (h-1) and has level h filled from left to right
What characterizes a full binary tree of height h?
All leaves are at level h and all other nodes each have 2 children
In a binary tree, what characterizes a node at level h-1 in a complete binary tree?
Each node has 2 children
What is the maximum height of an ill-balanced tree of size n?
n
How will an ill-balanced binary tree perform?
Like a linear data structure
What is the minimum number of nodes a balanced binary tree of height 4 can have?
8
What is the maximum height of a balanced binary tree with 63 nodes?
6
How many nodes can a balanced binary tree of height 6 have at most?
127
What is the minimum number of nodes a balanced binary tree of height h has?
2^(h-1)
What is the formula to calculate the height of a balanced binary tree of size n?
log2(n) + 1
What is the maximum number of nodes a balanced binary tree of height h can have?
2^h - 1
What is the time complexity for searching, sorting, insertion, and deletion operations in a balanced binary tree?
O(log n)
What is the time complexity for accessing any node in an ill-balanced binary tree?
O(n)
What kind of elements does the left subtree of a node in a binary sorted tree contain?
Elements less than or equals to the node element
What does a node in the right subtree of a node in a binary sorted tree contain?
Elements greater than the node element
What is the defining characteristic of a binary sorted tree?
Left subtree contains elements less than or equals to the node element, and right subtree contains elements greater than the node element
What action should be taken if the target element in a binary search tree is greater than the node element?
Go down the right subtree
What is the next step if the target element in a binary search tree is less than or equal to the node element?
Go down the left subtree
What is the iterative process for finding a target element in a binary search tree?
Compare, go left or right, repeat until found
What does the constructor of BSTreeNode take as parameters?
Element value, left child, and right child
Which methods would you expect to find in the BSTreeNode class for accessing the left and right children?
getLeft() and getRight()
What type of data does the element variable in the BSTreeNode class store?
Generic type (E)
How would you initialize a new leaf node with the element value '42'?
new BSTreeNode(42, null, null)
What happens when a node in a B-tree becomes full?
It needs to split into 2 nodes
Which method would you use to insert a new element into a binary search tree through a BSTreeNode instance?
insertElement(E elem)
If you want to traverse the elements of a binary search tree in an in-order fashion, which method would you typically use in the BSTreeNode class?
inOrderTraversal()
How would you check if a specific element exists in a binary search tree represented by a BSTreeNode instance?
containsElement(E elem)
What method might you use to remove a specific element from a binary search tree through a BSTreeNode instance?
removeElement(E elem)
What is the purpose of the parameterless constructor public BSTree() in the BSTree class?
It initializes an empty BST.
How is the root of the binary search tree initialized in the parameterized constructor public BSTree(E element)?
this.root = new BSTreeNode(element, null, null);
How would you check if a BSTree instance is empty?
isEmpty()
How would you create an empty binary search tree using the BSTree class?
BSTree emptyTree = new BSTree();
Test your knowledge of binary tree properties with this quiz! Explore concepts such as balanced, proper, full, and complete binary trees, and deepen your understanding of their unique characteristics.
Make Your Own Quizzes and Flashcards
Convert your notes into interactive study material.
Get started for free
