Количество пар, нарушающих свойство 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);