Количество пар, нарушающих свойство BST
Опубликовано: 5 Января, 2022
Учитывая двоичное дерево и количество узлов в дереве, задача состоит в том, чтобы найти количество пар, нарушающих свойство BST . Двоичное дерево поиска - это структура данных двоичного дерева на основе узлов, которая имеет следующие свойства:
- Левое поддерево узла содержит только узлы с ключами меньше ключа узла.
- Правое поддерево узла содержит только узлы с ключами больше ключа узла.
- Левое и правое поддерево также должны быть двоичным деревом поиска.
Примеры:
Вход: 4 / 5 6 Выход: 1 Для приведенного выше двоичного дерева пара (5, 4) нарушают свойство BST. Таким образом, посчитайте пар, нарушающих свойство BST, равно 1. Вход: 50 / 30 60 / / 20 25 10 40 Выход: 7 Для приведенного выше двоичного дерева пары (20, 10), (25, 10), (30, 25), (30, 10), (50, 10), (50, 40), (60, 40) нарушают свойство BST. Таким образом, количество пар, нарушающих свойство BST 7.
Рекомендуется: сначала решите эту проблему на «ПРАКТИКЕ», прежде чем переходить к решению.
Подход:
- Сохраните неупорядоченный обход двоичного дерева в массиве.
- Теперь посчитайте все пары так, чтобы a [i]> a [j] для i <j, которое является числом инверсий в массиве.
- Выведите количество пар, нарушающих свойство BST .
Ниже представлена реализация описанного выше подхода:
Джава
// Java program to count number of pairs // in a binary tree violating the BST property import java.io.*; import java.util.*; // Class that represents a node of the tree class Node { data; int Node left, right; // Constructor to create a new tree node Node( key) int { data = key; left = right = null ; } } class GFG { // This method sorts the input array and returns the // number of inversions in the array static int mergeSort( int arr[], int array_size) { int temp[] = new int [array_size]; return _mergeSort(arr, temp, 0 , array_size - 1 ); } // An auxiliary recursive method that sorts // the input array and returns the number of // inversions in the array static int _mergeSort( int arr[], int temp[], int left, int right) { int mid, inv_count = 0 ; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() for each // of the parts mid = (right + left) / 2 ; // Inversion count will be sum of inversions // in left-part, right-part and number of // inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1 , right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1 , right); } return inv_count; } // This method merges two sorted arrays and returns // inversion count in the arrays static merge( int int arr[], int temp[], int left, int mid, int right) { int i, j, k; int inv_count = 0 ; // i is index for left subarray i = left; // j is index for right subarray j = mid; // k is index for resultant merged subarray k = left; while ((i <= mid - 1 ) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } // Copy the remaining elements of left subarray // (if there are any) to temp while (i <= mid - 1 ) temp[k++] = arr[i++]; // Copy the remaining elements of right subarray // if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } // Array to store // inorder traversal of the binary tree static int [] a; static int in; // Inorder traversal of the binary tree static void Inorder(Node node) { if (node == null ) return ; Inorder(node.left); a[in++] = node.data; Inorder(node.right); } // Function to count the pairs // in a binary tree violating BST property static int pairsViolatingBST(Node root, int N) { if (root == null ) return 0 ; in = 0 ; a = new int [N]; Inorder(root); // Total inversions in the array int inversionCount = mergeSort(a, N); return inversionCount; } // Driver code public static void main(String args[]) { int N = 7 ; Node root = new Node( 50 ); root.left = new Node( 30 ); root.right = new Node( 60 ); root.left.left = new Node( 20 ); root.left.right = new Node( 25 ); root.right.left = new Node( 10 ); root.right.right = new Node( 40 ); System.out.println(pairsViolatingBST(root, N)); } } |
Python3
# Python3 program to count number of pairs # in a binary tree violating the BST property # Class that represents a node of the tree class newNode: def __init__( self , key): self .data = key self .left = None self .right = None # Array to store # inorder traversal of the binary tree a = [] id = 0 # This method sorts the input array # and returns the number of inversions # in the array def mergeSort(array_size): temp = [ 0 ] * array_size return _mergeSort(temp, 0 , array_size - 1 ) # An auxiliary recursive method that sorts # the input array and returns the number of # inversions in the array def _mergeSort(temp, left, right): inv_count = 0 if (right > left): # Divide the array into two parts and # call _mergeSortAndCountInv() for each # of the parts mid = (right + left) / / 2 # Inversion count will be sum of inversions # in left-part, right-part and number of # inversions in merging inv_count = _mergeSort(temp, left, mid) inv_count + = _mergeSort(temp, mid + 1 , right) # Merge the two parts inv_count + = merge(temp, left, mid + 1 , right) return inv_count # This method merges two sorted arrays # and returns inversion count in the arrays def merge(temp, left, mid, right): global a inv_count = 0 # i is index for left subarray i = left # j is index for right subarray j = mid # k is index for resultant merged subarray k = left while ((i < = mid - 1 ) and (j < = right)): if (a[i] < = a[j]): temp[k] = a[i] k + = 1 i + = 1 else : temp[k] = a[j] k + = 1 j + = 1 inv_count = inv_count + (mid - i) # Copy the remaining elements of left # subarray (if there are any) to temp while (i < = mid - 1 ): temp[k] = a[i] k + = 1 i + = 1 # Copy the remaining elements of right # subarray if there are any) to temp while (j < = right): temp[k] = a[j] k + = 1 j + = 1 # Copy back the merged elements # to original array for i in range (left, right + 1 , 1 ): a[i] = temp[i] return inv_count # Inorder traversal of the binary tree def Inorder(node): global a global id if (node = = None ): return Inorder(node.left) a.append(node.data) id + = 1 Inorder(node.right) # Function to count the pairs # in a binary tree violating # BST property def pairsViolatingBST(root, N): if (root = = None ): return 0 Inorder(root) # Total inversions in the array inversionCount = mergeSort(N) return inversionCount # Driver code if __name__ = = '__main__' : N = 7 root = newNode( 50 ) root.left = newNode( 30 ) root.right = newNode( 60 ) root.left.left = newNode( 20 ) root.left.right = newNode( 25 ) root.right.left = newNode( 10 ) root.right.right = newNode( 40 ) print (pairsViolatingBST(root, N)) # This code is contributed by bgangwar59 |
C #
// C# program to count number of pairs // in a binary tree violating the BST property using System; // Class that represents a node of the tree public class Node { public data; int public Node left, right; // Constructor to create a new tree node public Node( key) int { data = key; left = right = null ; } } class GFG { // This method sorts the input array and returns the // number of inversions in the array static int mergeSort( int [] arr, int array_size) { int [] temp = new int [array_size]; return _mergeSort(arr, temp, 0, array_size - 1); } // An auxiliary recursive method that sorts // the input array and returns the number of // inversions in the array static int _mergeSort( int [] arr, int [] temp, int left, int right) { int mid, inv_count = 0; if (right > left) { // Divide the array into two parts and // call _mergeSortAndCountInv() for each // of the parts mid = (right + left) / 2; // Inversion count will be sum of inversions // in left-part, right-part and number of // inversions in merging inv_count = _mergeSort(arr, temp, left, mid); inv_count += _mergeSort(arr, temp, mid + 1, right); // Merge the two parts inv_count += merge(arr, temp, left, mid + 1, right); } return inv_count; } // This method merges two sorted arrays and returns // inversion count in the arrays static merge( int int [] arr, int [] temp, int left, int mid, int right) { int i, j, k; int inv_count = 0; // i is index for left subarray i = left; // j is index for right subarray j = mid; // k is index for resultant merged subarray k = left; while ((i <= mid - 1) && (j <= right)) { if (arr[i] <= arr[j]) { temp[k++] = arr[i++]; } else { temp[k++] = arr[j++]; inv_count = inv_count + (mid - i); } } // Copy the remaining elements of left subarray // (if there are any) to temp while (i <= mid - 1) temp[k++] = arr[i++]; // Copy the remaining elements of right subarray // if there are any) to temp while (j <= right) temp[k++] = arr[j++]; // Copy back the merged elements to original array for (i = left; i <= right; i++) arr[i] = temp[i]; return inv_count; } // Array to store // inorder traversal of the binary tree static int [] a; static int i; // Inorder traversal of the binary tree static void Inorder(Node node) { if (node == null ) return ; Inorder(node.left); a[i++] = node.data; Inorder(node.right); } // Function to count the pairs // in a binary tree violating BST property static int pairsViolatingBST(Node root, int N) { if (root == null ) return 0; i = 0; a = new int [N]; Inorder(root); // Total inversions in the array int inversionCount = mergeSort(a, N); return inversionCount; } // Driver code public static void Main(String[] args) { int N = 7; Node root = new Node(50); root.left = new Node(30); root.right = new Node(60); root.left.left = new Node(20); root.left.right = new Node(25); РЕКОМЕНДУЕМЫЕ СТАТЬИ |