Nonlinear Data Structures - Tree Concepts

A tree is a finite set of one or more nodes that shows a parent-child relation where there is a specially designated node called the root. The remaining nodes are partitioned into disjoint subsets, each of which is a subtree.

The root node is the topmost node in the tree. It has no parent node.

Subtrees are the children of the root node of a tree and are themselves trees.

<p>A child node is a node that is directly connected to a parent node.</p> Signup and view all the answers

<p>Nodes that share the same parent node are called siblings.</p> Signup and view all the answers

<p>An ancestor node is a node that is found on the path from the root node to a target node.</p> Signup and view all the answers

<p>A descendant node is a node that is found below a parent node in the path towards a leaf node.</p> Signup and view all the answers

<p>A left subtree is a subtree that is connected to the left of a root node. It contains all the left descendants of the root node.</p> Signup and view all the answers

<p>A right subtree is a subtree that is connected to the right of a root node. It contains all the right descendants of the root node.</p> Signup and view all the answers

<p>The degree of a node is the number of subtrees connected to it</p> Signup and view all the answers

<p>A leaf node is a node in a tree that has a degree of zero, meaning it has no subtrees.</p> Signup and view all the answers

<p>An internal node is any node in a tree that is not a leaf node. It has at least one subtree.</p> Signup and view all the answers

<p>The level of a node is determined by the distance from the root node. The root node is at level 0 and each level increases by 1 as you move down the tree.</p> Signup and view all the answers

<p>The height or depth of a tree is determined by the maximum level of any leaf node in the tree.</p> Signup and view all the answers

<p>A binary tree is a tree data structure in which each node has at most two children: a left child and a right child. It is either empty or consists of a root node and two subtrees.</p> Signup and view all the answers

<p>A binary tree can be partitioned into three subgroups: root, left subtree, and right subtree.</p> Signup and view all the answers

<p>The 'info' field is where actual data or information is stored to be manipulated within the tree data structure.</p> Signup and view all the answers

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

<p>A strictly binary tree, also known as a full binary tree, is a binary tree where every internal node has either two children or zero children.</p> Signup and view all the answers

<p>A complete binary tree is a binary tree where every level, except possibly the last level, is completely filled. If the last level is not completely filled, then all nodes are filled from left to right.</p> Signup and view all the answers

<p>A skewed tree is a binary tree that has only a left subtree or only a right subtree.</p> Signup and view all the answers

<p>An expression tree is a binary tree where each internal node represents an operator and each leaf node represents an operand. It is used to represent mathematical expressions.</p> Signup and view all the answers

<p>A binary search tree is a binary tree where the keys in each node are sorted in a specific order, making searching for elements very efficient.</p> Signup and view all the answers

<p>An array representation of a binary tree uses a static allocation technique, where each node is stored in a specific location of the array.</p> Signup and view all the answers

<p>A linked representation of a binary tree uses a dynamic allocation technique, where each node points to its child nodes through pointers.</p> Signup and view all the answers

<p>In a pre-order traversal, you visit the root node first, then traverse the left subtree in pre-order, and finally traverse the right subtree in pre-order.</p> Signup and view all the answers

<p>Threaded binary trees are used to overcome the disadvantages of traditional binary trees, such as wasted memory due to null values and time-consuming traversal.</p> Signup and view all the answers

<p>The two types of threaded binary trees are one-way threaded binary trees, which use threads for only one direction, and two-way threaded binary trees, which use threads for both directions.</p> Signup and view all the answers

<p>A graph data structure is used to represent relationships or connections between entities, which are represented as vertices or nodes. The connections between the entities are represented as edges.</p> Signup and view all the answers

<p>A directed graph, also called a digraph, is a graph where each edge has a specific direction, indicating a one-way relationship between the connected vertices.</p> Signup and view all the answers

<p>A vertex, or node, is a fundamental component of a graph, representing a specific entity or data point.</p> Signup and view all the answers

<p>A self-loop is an edge that starts and ends on the same vertex in a graph, indicating a connection to itself.</p> Signup and view all the answers

<p>A multigraph is a graph that allows multiple edges connecting the same pair of vertices, representing multiple relationships between them.</p> Signup and view all the answers

<p>A complete graph is a graph where every pair of vertices is connected by a single edge. Each vertex is directly connected to all other vertices.</p> Signup and view all the answers

<p>A path in an undirected graph is a sequence of adjacent vertices, where the connection between each vertex is represented by an edge in the graph.</p> Signup and view all the answers

<p>A walk is a sequence of vertices and edges in a graph, where you can traverse the graph and visit the vertices and edges in a defined order.</p> Signup and view all the answers

<p>A simple path is a path where all vertices, except possibly the first and last vertices, are distinct, and the connection between them is represented by an edge in the graph.</p> Signup and view all the answers

<p>The length of a path in a graph is equal to the number of edges present in the path.</p> Signup and view all the answers

<p>A cycle or circuit is a path in a graph where the starting and ending vertices are the same. This means that you can travel through the path and end up back where you started.</p> Signup and view all the answers

<p>A cyclic graph is a graph that contains at least one cycle.</p> Signup and view all the answers

<p>A disconnected graph is a graph where there is not a path between every pair of vertices. This means that some vertices may be isolated or not connected to others.</p> Signup and view all the answers

<p>A component is a connected subgraph within a disconnected graph.</p> Signup and view all the answers

<p>An adjacency matrix is a square matrix that represents a graph. The rows and columns of the matrix correspond to the vertices, and the value in each cell indicates the presence or absence of an edge between the corresponding vertices.</p> Signup and view all the answers

<p>An adjacency list is an array of linked lists, where each location in the array represents a vertex in the graph. Each linked list contains the vertices that are adjacent to the corresponding vertex.</p> Signup and view all the answers

<p>A weighted graph is a graph where each edge has an associated weight value, representing the cost, distance, or strength of connecting the vertices.</p> Signup and view all the answers

<p>An Euler path is a path in a graph that traverses each edge of the graph exactly once.</p> Signup and view all the answers

<p>An Euler circuit is a circuit in a graph that traverses each edge exactly once and ends at the same vertex it started at.</p> Signup and view all the answers

<p>A connected graph has an Euler circuit only if each vertex has an even degree, meaning each vertex has an even number of edges connected to it.</p> Signup and view all the answers

<p>A connected graph has an Euler path if and only if it has exactly two vertices with an odd degree. The starting and ending vertices must be distinct.</p> Signup and view all the answers

<p>A Hamiltonian circuit is a circuit that visits each vertex exactly once, with no repeats, and ends at the same vertex it started at.</p> Signup and view all the answers

<p>A Hamiltonian path is a path that visits each vertex exactly once, with no repeats, but does not end at the same vertex it started at.</p> Signup and view all the answers

<p>Hashing is a technique used for indexing and retrieving data in a data structure, providing a faster way to find elements by using a hash key.</p> Signup and view all the answers

<p>A hash key is a unique value generated for each data element using a hash function. This key maps the element to a specific location in a hash table, allowing for fast retrieval.</p> Signup and view all the answers

<p>A hash function is a function that takes a piece of data as input and produces an integer value as output. This integer maps the data to a specific location in a hash table.</p> Signup and view all the answers

<p>Hash functions are used to map data to a unique integer value (hash key). This value is then used to store the data in a specific location in the hash table, allowing for efficient retrieval of the data based on its corresponding key.</p> Signup and view all the answers

<p>Collision in hashing occurs when two or more data elements are mapped to the same location in the hash table, even though they have different keys.</p> Signup and view all the answers

<p>Closed hashing, also known as open addressing, is a collision resolution technique where all keys are stored directly in the hash table itself. When a collision occurs, a different location in the hash table is found using different probing techniques, ensuring that each key has a unique location.</p> Signup and view all the answers

<p>Linear probing is a simple probing technique used in closed hashing to resolve collisions. When a collision occurs, it checks the next available space in the hash table. If the next space is also occupied, it continues to probe linearly until it finds an empty space.</p> Signup and view all the answers

<p>Overflow in hashing occurs when the hash table becomes completely full, or when the data structure used to handle collisions, like a linked list in open hashing, exceeds its capacity.</p> Signup and view all the answers

<p>Overflow in hashing can be handled by resizing the hash table to increase its capacity, using a more efficient hash function, or employing a different collision resolution technique that uses a more appropriate data structure for handling collisions.</p> Signup and view all the answers