Binary Tree Properties Quiz
64 Questions
3 Views

Choose a study mode

Play Quiz
Study Flashcards
Spaced Repetition
Chat to lesson

Podcast

Play an AI-generated podcast conversation about this lesson

Questions and Answers

In a binary sorted tree, what type of elements does the left subtree of a node contain?

  • Elements greater than the node element
  • Elements less than or equals to the node element (correct)
  • Elements equals to the node element
  • Elements greater 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 (correct)
  • Move to the parent node
  • Down the right subtree
  • Stay at the current node

    • What does the BSTree Java class constructor with no parameters do?

  • Creates a binary sorted tree with a single node
  • Constructs an empty binary sorted tree (correct)
  • Throws an exception
  • Initializes the root node with a null element

    • What does the BSTreeNode Java class represent?

    <p>Nodes in a binary sorted tree</p> Signup and view all the answers

    What defines a balanced binary tree?

    <p>The height difference between the left and right subtrees of every node is at most 1</p> Signup and view all the answers

    How is the maximum number of nodes for a binary tree of height 1 determined?

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

    What characterizes a proper binary tree?

    <p>Each node has either 0 or 2 children</p> Signup and view all the answers

    What is the height of a balanced binary tree of size n?

    <p>$\lfloor \log_2 n \rfloor + 1$</p> Signup and view all the answers

    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?

    <p>Upheap node values to its rightful place in the tree</p> Signup and view all the answers

    In heap deletion, what is the condition for swapping a child node with the new node in a max heap?

    <p>If child node is greater than the new node</p> Signup and view all the answers

    What type of deletion is allowed in a heap data structure?

    <p>Restricted deletion called extraction</p> Signup and view all the answers

    What is the time complexity of a well-balanced tree for insertion and deletion operations?

    <p>O(log n)</p> Signup and view all the answers

    How does each insertion and deletion operation affect the balance of a tree?

    <p>They affect the balance of the tree</p> Signup and view all the answers

    What is the objective in maintaining the balance of a tree after each operation?

    <p>To keep the height of the tree to a minimum</p> Signup and view all the answers

    What does the balance of a node in a tree represent?

    <p>The height of the right sub-tree minus the height of the left sub-tree</p> Signup and view all the answers

    How is the balance of a node calculated in a tree?

    <p>Balance(n) = right-height(n) - left-height(n)</p> Signup and view all the answers

    In a balanced binary tree, what is the relationship between the heights of the left and right sub-trees of a node?

    <p>The heights are such that the absolute difference is at most 1</p> Signup and view all the answers

    What is the maximum number of nodes and elements on level 3 of a B-Tree of order 100?

    <p>Nodes: 202, Elements: 40,401</p> Signup and view all the answers

    What variant of B-Tree facilitates sequential access of a file by having pointers in leaf nodes to the next sibling?

    <p>B+Tree</p> Signup and view all the answers

    What percentage of fullness do B*Trees operate at on average?

    <p>81%</p> Signup and view all the answers

    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?

    <p>The resulting B-Tree after adding the given sequence</p> Signup and view all the answers

    When does a node in a B-tree need to split into 2 nodes?

    <p>When it has more than 2n elements</p> Signup and view all the answers

    What happens when a node in a B-tree becomes full?

    <p>It must split into 2 nodes</p> Signup and view all the answers

    What happens when a new element needs to be added to a full B-tree with a full root node?

    <p>The root node is split and a new root node is created</p> Signup and view all the answers

    What is the objective in maintaining the balance of a binary tree?

    <p>To optimize search and insertion operations</p> Signup and view all the answers

    What is the purpose of B-trees in the context of hierarchical abstract data types?

    <p>Efficiently handle large amounts of data and minimize disk access</p> Signup and view all the answers

    When discussing hierarchical abstract data types, what does a balanced binary tree aim to achieve?

    <p>Minimize the height disparity between left and right subtrees</p> Signup and view all the answers

    How is the size of a tree defined?

    <p>The total number of nodes</p> Signup and view all the answers

    What is a characteristic of a node in a tree?

    <p>A node must have only one unique path from the root</p> Signup and view all the answers

    What does the height of a tree represent?

    <p>The number of levels with nodes</p> Signup and view all the answers

    What forms the left and right subtrees in a binary tree?

    <p>Left child and its descendants for the left subtree, right child and its descendants for the right subtree</p> Signup and view all the answers

    What is the maximum number of children a node can have in a binary tree?

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

    What characterizes a complete binary tree of height h?

    <p>It is full to level (h-1) and has level h filled from left to right</p> Signup and view all the answers

    What characterizes a full binary tree of height h?

    <p>All leaves are at level h and all other nodes each have 2 children</p> Signup and view all the answers

    In a binary tree, what characterizes a node at level h-1 in a complete binary tree?

    <p>Each node has 2 children</p> Signup and view all the answers

    What is the maximum height of an ill-balanced tree of size n?

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

    How will an ill-balanced binary tree perform?

    <p>Like a linear data structure</p> Signup and view all the answers

    What is the minimum number of nodes a balanced binary tree of height 4 can have?

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

    What is the maximum height of a balanced binary tree with 63 nodes?

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

    How many nodes can a balanced binary tree of height 6 have at most?

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

    What is the minimum number of nodes a balanced binary tree of height h has?

    <p>2^(h-1)</p> Signup and view all the answers

    What is the formula to calculate the height of a balanced binary tree of size n?

    <p>log2(n) + 1</p> Signup and view all the answers

    What is the maximum number of nodes a balanced binary tree of height h can have?

    <p>2^h - 1</p> Signup and view all the answers

    What is the time complexity for searching, sorting, insertion, and deletion operations in a balanced binary tree?

    <p>O(log n)</p> Signup and view all the answers

    What is the time complexity for accessing any node in an ill-balanced binary tree?

    <p>O(n)</p> Signup and view all the answers

    What kind of elements does the left subtree of a node in a binary sorted tree contain?

    <p>Elements less than or equals to the node element</p> Signup and view all the answers

    What does a node in the right subtree of a node in a binary sorted tree contain?

    <p>Elements greater than the node element</p> Signup and view all the answers

    What is the defining characteristic of a binary sorted tree?

    <p>Left subtree contains elements less than or equals to the node element, and right subtree contains elements greater than the node element</p> Signup and view all the answers

    What action should be taken if the target element in a binary search tree is greater than the node element?

    <p>Go down the right subtree</p> Signup and view all the answers

    What is the next step if the target element in a binary search tree is less than or equal to the node element?

    <p>Go down the left subtree</p> Signup and view all the answers

    What is the iterative process for finding a target element in a binary search tree?

    <p>Compare, go left or right, repeat until found</p> Signup and view all the answers

    What does the constructor of BSTreeNode take as parameters?

    <p>Element value, left child, and right child</p> Signup and view all the answers

    Which methods would you expect to find in the BSTreeNode class for accessing the left and right children?

    <p>getLeft() and getRight()</p> Signup and view all the answers

    What type of data does the element variable in the BSTreeNode class store?

    <p>Generic type (E)</p> Signup and view all the answers

    How would you initialize a new leaf node with the element value '42'?

    <p>new BSTreeNode(42, null, null)</p> Signup and view all the answers

    What happens when a node in a B-tree becomes full?

    <p>It needs to split into 2 nodes</p> Signup and view all the answers

    Which method would you use to insert a new element into a binary search tree through a BSTreeNode instance?

    <p>insertElement(E elem)</p> Signup and view all the answers

    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?

    <p>inOrderTraversal()</p> Signup and view all the answers

    How would you check if a specific element exists in a binary search tree represented by a BSTreeNode instance?

    <p>containsElement(E elem)</p> Signup and view all the answers

    What method might you use to remove a specific element from a binary search tree through a BSTreeNode instance?

    <p>removeElement(E elem)</p> Signup and view all the answers

    What is the purpose of the parameterless constructor public BSTree() in the BSTree class?

    <p>It initializes an empty BST.</p> Signup and view all the answers

    How is the root of the binary search tree initialized in the parameterized constructor public BSTree(E element)?

    <p>this.root = new BSTreeNode(element, null, null);</p> Signup and view all the answers

    How would you check if a BSTree instance is empty?

    <p>isEmpty()</p> Signup and view all the answers

    How would you create an empty binary search tree using the BSTree class?

    <p>BSTree emptyTree = new BSTree();</p> Signup and view all the answers

    More Like This

    Use Quizgecko on...
    Browser
    Open
    Browser
    Browser