Dado un árbol de búsqueda binaria y un número entero K , tenemos que dividir el árbol en dos árboles de búsqueda binaria equilibrados , donde BST-1 consta de todos los Nodes que son menores que K y BST-2 consta de todos los Nodes que son mayores que o igual a K.
Nota: La disposición de los Nodes puede ser cualquier cosa, pero ambos BST deben estar equilibrados.
Ejemplos:
Input:
40
/ \
20 50
/ \ \
10 35 60
/ /
25 55
K = 35
Output:
First BST: 10 20 25
Second BST: 35 40 50 55 60
Explanation:
After splitting above BST
about given value K = 35
First Balanced Binary Search Tree is
20
/ \
10 25
Second Balanced Binary Search Tree is
50
/ \
35 55
\ \
40 60
OR
40
/ \
35 55
/ \
50 60
Input:
100
/ \
20 500
/ \
10 30
\
40
K = 50
Output:
First BST: 10 20 30 40
Second BST: 100 500
Explanation:
After splitting above BST
about given value K = 50
First Balanced Binary Search Tree is
20
/ \
10 30
\
40
Second Balanced Binary Search Tree is
100
\
500
Acercarse:
- Primero almacene el recorrido en orden de BST dado en una array
- Luego, divida esta array sobre el valor dado K
- Ahora construya el primer BST balanceado por la primera parte dividida y el segundo BST por la segunda parte dividida, utilizando el enfoque utilizado en este artículo .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to split a BST into
// two balanced BSTs based on a value K
#include <iostream>
using namespace std;
// Structure of each node of BST
struct node {
int key;
struct node *left, *right;
};
// A utility function to
// create a new BST node
node* newNode(int item)
{
node* temp = new node();
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
// A utility function to insert a new
// node with given key in BST
struct node* insert(struct node* node,
int key)
{
// If the tree is empty, return a new node
if (node == NULL)
return newNode(key);
// Otherwise, recur down the tree
if (key < node->key)
node->left = insert(node->left,
key);
else if (key > node->key)
node->right = insert(node->right,
key);
// return the (unchanged) node pointer
return node;
}
// Function to return the size
// of the tree
int sizeOfTree(node* root)
{
if (root == NULL) {
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root->left);
// Calculate right size recursively
int right = sizeOfTree(root->right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
void storeInorder(node* root,
int inOrder[],
int& index)
{
// Base condition
if (root == NULL) {
return;
}
// Left recursive call
storeInorder(root->left,
inOrder, index);
// Store elements in inorder array
inOrder[index++] = root->key;
// Right recursive call
storeInorder(root->right,
inOrder, index);
}
// Function to return the splitting
// index of the array
int getSplittingIndex(int inOrder[],
int index, int k)
{
for (int i = 0; i < index; i++) {
if (inOrder[i] >= k) {
return i - 1;
}
}
return index - 1;
}
// Function to create the Balanced
// Binary search tree
node* createBST(int inOrder[],
int start, int end)
{
// Base Condition
if (start > end) {
return NULL;
}
// Calculate the mid of the array
int mid = (start + end) / 2;
node* t = newNode(inOrder[mid]);
// Recursive call for left child
t->left = createBST(inOrder,
start, mid - 1);
// Recursive call for right child
t->right = createBST(inOrder,
mid + 1, end);
// Return newly created Balanced
// Binary Search Tree
return t;
}
// Function to traverse the tree
// in inorder fashion
void inorderTrav(node* root)
{
if (root == NULL)
return;
inorderTrav(root->left);
cout << root->key << " ";
inorderTrav(root->right);
}
// Function to split the BST
// into two Balanced BST
void splitBST(node* root, int k)
{
// Print the original BST
cout << "Original BST : ";
if (root != NULL) {
inorderTrav(root);
}
else {
cout << "NULL";
}
cout << endl;
// Store the size of BST1
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST1
int inOrder[numNode + 1];
int index = 0;
// Function call for storing
// inorder traversal of BST1
storeInorder(root, inOrder, index);
// Function call for getting
// splitting index
int splitIndex
= getSplittingIndex(inOrder,
index, k);
node* root1 = NULL;
node* root2 = NULL;
// Creation of first Balanced
// Binary Search Tree
if (splitIndex != -1)
root1 = createBST(inOrder, 0,
splitIndex);
// Creation of Second Balanced
// Binary Search Tree
if (splitIndex != (index - 1))
root2 = createBST(inOrder,
splitIndex + 1,
index - 1);
// Print two Balanced BSTs
cout << "First BST : ";
if (root1 != NULL) {
inorderTrav(root1);
}
else {
cout << "NULL";
}
cout << endl;
cout << "Second BST : ";
if (root2 != NULL) {
inorderTrav(root2);
}
else {
cout << "NULL";
}
}
// Driver code
int main()
{
/* BST
5
/ \
3 7
/ \ / \
2 4 6 8
*/
struct node* root = NULL;
root = insert(root, 5);
insert(root, 3);
insert(root, 2);
insert(root, 4);
insert(root, 7);
insert(root, 6);
insert(root, 8);
int k = 5;
// Function to split BST
splitBST(root, k);
return 0;
}
Java
// Java program to split a BST into
// two balanced BSTs based on a value K
import java.util.*;
class GFG{
// Structure of each node of BST
static class node {
int key;
node left, right;
};
static int index;
// A utility function to
// create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new
// node with given key in BST
static node insert(node node,
int key)
{
// If the tree is empty, return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left,
key);
else if (key > node.key)
node.right = insert(node.right,
key);
// return the (unchanged) node pointer
return node;
}
// Function to return the size
// of the tree
static int sizeOfTree(node root)
{
if (root == null) {
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
static void storeInorder(node root,
int inOrder[])
{
// Base condition
if (root == null) {
return;
}
// Left recursive call
storeInorder(root.left,
inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
storeInorder(root.right,
inOrder);
}
// Function to return the splitting
// index of the array
static int getSplittingIndex(int inOrder[],
int k)
{
for (int i = 0; i < index; i++) {
if (inOrder[i] >= k) {
return i - 1;
}
}
return index - 1;
}
// Function to create the Balanced
// Binary search tree
static node createBST(int inOrder[],
int start, int end)
{
// Base Condition
if (start > end) {
return null;
}
// Calculate the mid of the array
int mid = (start + end) / 2;
node t = newNode(inOrder[mid]);
// Recursive call for left child
t.left = createBST(inOrder,
start, mid - 1);
// Recursive call for right child
t.right = createBST(inOrder,
mid + 1, end);
// Return newly created Balanced
// Binary Search Tree
return t;
}
// Function to traverse the tree
// in inorder fashion
static void inorderTrav(node root)
{
if (root == null)
return;
inorderTrav(root.left);
System.out.print(root.key+ " ");
inorderTrav(root.right);
}
// Function to split the BST
// into two Balanced BST
static void splitBST(node root, int k)
{
// Print the original BST
System.out.print("Original BST : ");
if (root != null) {
inorderTrav(root);
}
else {
System.out.print("null");
}
System.out.println();
// Store the size of BST1
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST1
int []inOrder = new int[numNode + 1];
index = 0;
// Function call for storing
// inorder traversal of BST1
storeInorder(root, inOrder);
// Function call for getting
// splitting index
int splitIndex
= getSplittingIndex(inOrder,
k);
node root1 = null;
node root2 = null;
// Creation of first Balanced
// Binary Search Tree
if (splitIndex != -1)
root1 = createBST(inOrder, 0,
splitIndex);
// Creation of Second Balanced
// Binary Search Tree
if (splitIndex != (index - 1))
root2 = createBST(inOrder,
splitIndex + 1,
index - 1);
// Print two Balanced BSTs
System.out.print("First BST : ");
if (root1 != null) {
inorderTrav(root1);
}
else {
System.out.print("null");
}
System.out.println();
System.out.print("Second BST : ");
if (root2 != null) {
inorderTrav(root2);
}
else {
System.out.print("null");
}
}
// Driver code
public static void main(String[] args)
{
/* BST
5
/ \
3 7
/ \ / \
2 4 6 8
*/
node root = null;
root = insert(root, 5);
insert(root, 3);
insert(root, 2);
insert(root, 4);
insert(root, 7);
insert(root, 6);
insert(root, 8);
int k = 5;
// Function to split BST
splitBST(root, k);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python 3 program to split a
# BST into two balanced BSTs
# based on a value K
index = 0
# Structure of each node of BST
class newNode:
def __init__(self, item):
# A utility function to
# create a new BST node
self.key = item
self.left = None
self.right = None
# A utility function to insert
# a new node with given key
# in BST
def insert(node, key):
# If the tree is empty,
# return a new node
if (node == None):
return newNode(key)
# Otherwise, recur down
# the tree
if (key < node.key):
node.left = insert(node.left,
key)
elif (key > node.key):
node.right = insert(node.right,
key)
# return the (unchanged)
# node pointer
return node
# Function to return the
# size of the tree
def sizeOfTree(root):
if (root == None):
return 0
# Calculate left size
# recursively
left = sizeOfTree(root.left)
# Calculate right size
# recursively
right = sizeOfTree(root.right)
# Return total size
# recursively
return (left + right + 1)
# Function to store inorder
# traversal of BST
def storeInorder(root, inOrder):
global index
# Base condition
if (root == None):
return
# Left recursive call
storeInorder(root.left,
inOrder)
# Store elements in
# inorder array
inOrder[index] = root.key
index += 1
# Right recursive call
storeInorder(root.right,
inOrder)
# Function to return the
# splitting index of the
# array
def getSplittingIndex(inOrder,
index, k):
for i in range(index):
if (inOrder[i] >= k):
return i - 1
return index - 1
# Function to create the
# Balanced Binary search
# tree
def createBST(inOrder,
start, end):
# Base Condition
if (start > end):
return None
# Calculate the mid of
# the array
mid = (start + end) // 2
t = newNode(inOrder[mid])
# Recursive call for
# left child
t.left = createBST(inOrder,
start,
mid - 1)
# Recursive call for
# right child
t.right = createBST(inOrder,
mid + 1, end)
# Return newly created
# Balanced Binary Search
# Tree
return t
# Function to traverse
# the tree in inorder
# fashion
def inorderTrav(root):
if (root == None):
return
inorderTrav(root.left)
print(root.key, end = " ")
inorderTrav(root.right)
# Function to split the BST
# into two Balanced BST
def splitBST(root, k):
global index
# Print the original BST
print("Original BST : ")
if (root != None):
inorderTrav(root)
print("\n", end = "")
else:
print("NULL")
# Store the size of BST1
numNode = sizeOfTree(root)
# Take auxiliary array for
# storing The inorder traversal
# of BST1
inOrder = [0 for i in range(numNode + 1)]
index = 0
# Function call for storing
# inorder traversal of BST1
storeInorder(root, inOrder)
# Function call for getting
# splitting index
splitIndex = getSplittingIndex(inOrder,
index, k)
root1 = None
root2 = None
# Creation of first Balanced
# Binary Search Tree
if (splitIndex != -1):
root1 = createBST(inOrder,
0, splitIndex)
# Creation of Second Balanced
# Binary Search Tree
if (splitIndex != (index - 1)):
root2 = createBST(inOrder,
splitIndex + 1,
index - 1)
# Print two Balanced BSTs
print("First BST : ")
if (root1 != None):
inorderTrav(root1)
print("\n", end = "")
else:
print("NULL")
print("Second BST : ")
if (root2 != None):
inorderTrav(root2)
print("\n", end = "")
else:
print("NULL")
# Driver code
if __name__ == '__main__':
'''/* BST
5
/ /
3 7
/ / / /
2 4 6 8
*/'''
root = None
root = insert(root, 5)
insert(root, 3)
insert(root, 2)
insert(root, 4)
insert(root, 7)
insert(root, 6)
insert(root, 8)
k = 5
# Function to split BST
splitBST(root, k)
# This code is contributed by Chitranayal
C#
// C# program to split a BST into
// two balanced BSTs based on a value K
using System;
public class GFG{
// Structure of each node of BST
public class node {
public int key;
public node left, right;
};
static int index;
// A utility function to
// create a new BST node
static node newNode(int item)
{
node temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new
// node with given key in BST
static node insert(node node,
int key)
{
// If the tree is empty, return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left,
key);
else if (key > node.key)
node.right = insert(node.right,
key);
// return the (unchanged) node pointer
return node;
}
// Function to return the size
// of the tree
static int sizeOfTree(node root)
{
if (root == null) {
return 0;
}
// Calculate left size recursively
int left = sizeOfTree(root.left);
// Calculate right size recursively
int right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
static void storeInorder(node root,
int []inOrder)
{
// Base condition
if (root == null) {
return;
}
// Left recursive call
storeInorder(root.left,
inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
storeInorder(root.right,
inOrder);
}
// Function to return the splitting
// index of the array
static int getSplittingIndex(int []inOrder,
int k)
{
for (int i = 0; i < index; i++) {
if (inOrder[i] >= k) {
return i - 1;
}
}
return index - 1;
}
// Function to create the Balanced
// Binary search tree
static node createBST(int []inOrder,
int start, int end)
{
// Base Condition
if (start > end) {
return null;
}
// Calculate the mid of the array
int mid = (start + end) / 2;
node t = newNode(inOrder[mid]);
// Recursive call for left child
t.left = createBST(inOrder,
start, mid - 1);
// Recursive call for right child
t.right = createBST(inOrder,
mid + 1, end);
// Return newly created Balanced
// Binary Search Tree
return t;
}
// Function to traverse the tree
// in inorder fashion
static void inorderTrav(node root)
{
if (root == null)
return;
inorderTrav(root.left);
Console.Write(root.key+ " ");
inorderTrav(root.right);
}
// Function to split the BST
// into two Balanced BST
static void splitBST(node root, int k)
{
// Print the original BST
Console.Write("Original BST : ");
if (root != null) {
inorderTrav(root);
}
else {
Console.Write("null");
}
Console.WriteLine();
// Store the size of BST1
int numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST1
int []inOrder = new int[numNode + 1];
index = 0;
// Function call for storing
// inorder traversal of BST1
storeInorder(root, inOrder);
// Function call for getting
// splitting index
int splitIndex
= getSplittingIndex(inOrder,
k);
node root1 = null;
node root2 = null;
// Creation of first Balanced
// Binary Search Tree
if (splitIndex != -1)
root1 = createBST(inOrder, 0,
splitIndex);
// Creation of Second Balanced
// Binary Search Tree
if (splitIndex != (index - 1))
root2 = createBST(inOrder,
splitIndex + 1,
index - 1);
// Print two Balanced BSTs
Console.Write("First BST : ");
if (root1 != null) {
inorderTrav(root1);
}
else {
Console.Write("null");
}
Console.WriteLine();
Console.Write("Second BST : ");
if (root2 != null) {
inorderTrav(root2);
}
else {
Console.Write("null");
}
}
// Driver code
public static void Main(String[] args)
{
/* BST
5
/ \
3 7
/ \ / \
2 4 6 8
*/
node root = null;
root = insert(root, 5);
insert(root, 3);
insert(root, 2);
insert(root, 4);
insert(root, 7);
insert(root, 6);
insert(root, 8);
int k = 5;
// Function to split BST
splitBST(root, k);
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// javascript program to split a BST into
// two balanced BSTs based on a value K
// Structure of each node of BST
class node {
constructor() {
this.key = 0;
this.left = this.right = null;
}
}
var index = 0;
// A utility function to
// create a new BST node
function newNode(item) {
var temp = new node();
temp.key = item;
temp.left = temp.right = null;
return temp;
}
// A utility function to insert a new
// node with given key in BST
function insert( node , key) {
// If the tree is empty, return a new node
if (node == null)
return newNode(key);
// Otherwise, recur down the tree
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
// return the (unchanged) node pointer
return node;
}
// Function to return the size
// of the tree
function sizeOfTree( root) {
if (root == null) {
return 0;
}
// Calculate left size recursively
var left = sizeOfTree(root.left);
// Calculate right size recursively
var right = sizeOfTree(root.right);
// Return total size recursively
return (left + right + 1);
}
// Function to store inorder
// traversal of BST
function storeInorder( root , inOrder) {
// Base condition
if (root == null) {
return;
}
// Left recursive call
storeInorder(root.left, inOrder);
// Store elements in inorder array
inOrder[index++] = root.key;
// Right recursive call
storeInorder(root.right, inOrder);
}
// Function to return the splitting
// index of the array
function getSplittingIndex(inOrder , k) {
for (i = 0; i < index; i++) {
if (inOrder[i] >= k) {
return i - 1;
}
}
return index - 1;
}
// Function to create the Balanced
// Binary search tree
function createBST(inOrder , start , end) {
// Base Condition
if (start > end) {
return null;
}
// Calculate the mid of the array
var mid = parseInt((start + end) / 2);
var t = newNode(inOrder[mid]);
// Recursive call for left child
t.left = createBST(inOrder, start, mid - 1);
// Recursive call for right child
t.right = createBST(inOrder, mid + 1, end);
// Return newly created Balanced
// Binary Search Tree
return t;
}
// Function to traverse the tree
// in inorder fashion
function inorderTrav( root) {
if (root == null)
return;
inorderTrav(root.left);
document.write(root.key + " ");
inorderTrav(root.right);
}
// Function to split the BST
// into two Balanced BST
function splitBST( root , k) {
// Print the original BST
document.write("Original BST : ");
if (root != null) {
inorderTrav(root);
} else {
document.write("null");
}
document.write();
// Store the size of BST1
var numNode = sizeOfTree(root);
// Take auxiliary array for storing
// The inorder traversal of BST1
var inOrder = Array(numNode + 1).fill(0);
index = 0;
// Function call for storing
// inorder traversal of BST1
storeInorder(root, inOrder);
// Function call for getting
// splitting index
var splitIndex = getSplittingIndex(inOrder, k);
var root1 = null;
var root2 = null;
// Creation of first Balanced
// Binary Search Tree
if (splitIndex != -1)
root1 = createBST(inOrder, 0, splitIndex);
// Creation of Second Balanced
// Binary Search Tree
if (splitIndex != (index - 1))
root2 = createBST(inOrder, splitIndex + 1, index - 1);
// Print two Balanced BSTs
document.write("<br/>First BST : ");
if (root1 != null) {
inorderTrav(root1);
} else {
document.write("null");
}
document.write();
document.write("<br/>Second BST : ");
if (root2 != null) {
inorderTrav(root2);
} else {
document.write("null");
}
}
// Driver code
/* BST
5
/ \
3 7
/ \ / \
2 4 6 8
*/
var root = null;
root = insert(root, 5);
insert(root, 3);
insert(root, 2);
insert(root, 4);
insert(root, 7);
insert(root, 6);
insert(root, 8);
var k = 5;
// Function to split BST
splitBST(root, k);
// This code contributed by Rajput-Ji
</script>
Producción:
Original BST : 2 3 4 5 6 7 8 First BST : 2 3 4 Second BST : 5 6 7 8
Publicación traducida automáticamente
Artículo escrito por MohammadMudassir y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA