Dado un árbol de búsqueda binario (BST) desequilibrado, la tarea es convertirlo en un BST equilibrado en tiempo lineal y sin usar espacio auxiliar.
Ejemplos:
Entrada: 5
/ \
1 10
\
20
\
35
Salida: 20
/ \
5 35
/ \
1 10Entrada: 10
/
5
/
2
/
1
Salida: 5
/ \
2 10
/
1
Enfoque: El algoritmo utilizado en este escenario es el algoritmo Day-Stout-Warren . El árbol balanceado formado será un árbol binario completo . Siga los pasos a continuación para la implementación del algoritmo.
- Paso 1 : Convierta el BST dado en una lista enlazada (lista enlazada del lado derecho) usando el concepto de rotaciones a la derecha por medio del recorrido en orden. Esta forma de BST se conoce como columna vertebral o vid . el tiempo de ejecución de esta fase es lineal y no se requiere espacio adicional.
La función está codificada de tal manera que realiza toda la rotación correcta requerida para aplanar el BST y al final devuelve el número de Nodes en BST. - Paso 2 : Calcule la altura de BST en la que todos los niveles se llenarán por completo utilizando la fórmula h = log2(N+1) [N es el número total de Nodes]. Y usando la altura calcule el número de Nodes que se pueden colocar en esa altura m = pow(2, h)-1 . [h es la altura hasta la cual todos los niveles están completamente llenos de Nodes]
La diferencia (diff) de N y m es la cantidad de Nodes que habrá en el último nivel del árbol binario completo balanceado. - La vid obtenida en el primer paso se deja luego rotar una cantidad diferente de tiempo desde su raíz. El árbol modificado anterior se gira a la izquierda m/2, m/4, m/8. . . veces hasta que m sea mayor que 0 según el algoritmo
Ilustraciones:
Ilustración-1: Aquí el árbol dado es un BST sesgado a la izquierda
Ejemplo 1
Ilustración-2: Aquí es un BST no sesgado pero desequilibrado
Ejemplo-2
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ code to balance BST using DSW algorithm.
#include <bits/stdc++.h>
using namespace std;
// Defining the structure for TreeNode.
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode()
: val(0)
, left(NULL)
, right(NULL)
{
}
TreeNode(int x)
: val(x)
, left(NULL)
, right(NULL)
{
}
TreeNode(int x, TreeNode* left,
TreeNode* right)
: val(x)
, left(left)
, right(right)
{
}
};
// Function to convert input BST
// to right linked list
// known as vine or backbone.
int bstToVine(TreeNode* grand)
{
int count = 0;
// Make tmp pointer to traverse
// and right flatten the given BST.
TreeNode* tmp = grand->right;
// Traverse until tmp becomes NULL
while (tmp) {
// If left exist for node
// pointed by tmp then
// right rotate it.
if (tmp->left) {
TreeNode* oldTmp = tmp;
tmp = tmp->left;
oldTmp->left = tmp->right;
tmp->right = oldTmp;
grand->right = tmp;
}
// If left dont exists
// add 1 to count and
// traverse further right to
// flatten remaining BST.
else {
count++;
grand = tmp;
tmp = tmp->right;
}
}
return count;
}
// Function to compress given tree
// with its root as grand->right.
void compress(TreeNode* grand, int m)
{
// Make tmp pointer to traverse
// and compress the given BST.
TreeNode* tmp = grand->right;
// Traverse and left-rotate root m times
// to compress given vine form of BST.
for (int i = 0; i < m; i++) {
TreeNode* oldTmp = tmp;
tmp = tmp->right;
grand->right = tmp;
oldTmp->right = tmp->left;
tmp->left = oldTmp;
grand = tmp;
tmp = tmp->right;
}
}
// Function to implement the algorithm
TreeNode* balanceBST(TreeNode* root)
{
// create dummy node with value 0
TreeNode* grand = new TreeNode(0);
// assign the right of dummy node as our input BST
grand->right = root;
// get the number of nodes in input BST and
// simultaneously convert it into right linked list.
int count = bstToVine(grand);
// gets the height of tree in which all levels
// are completely filled.
int h = log2(count + 1);
// get number of nodes until second last level
int m = pow(2, h) - 1;
// Left rotate for excess nodes at last level
compress(grand, count - m);
// Left rotation till m becomes 0
// Step is done as mentioned in algo to
// make BST balanced.
for (m = m / 2; m > 0; m /= 2) {
compress(grand, m);
}
// return the balanced tree
return grand->right;
}
// Function to print preorder traversal
// of Binary tree.
void preorderTraversal(TreeNode* root)
{
if (!root)
return;
cout << root->val << " ";
preorderTraversal(root->left);
preorderTraversal(root->right);
return;
}
// Driver code
int main()
{
TreeNode* root = new TreeNode(10);
root->left = new TreeNode(5);
root->left->left = new TreeNode(2);
root->left->left->left
= new TreeNode(1);
// Function call to implement
// Day-Stout-Warren algorithm
root = balanceBST(root);
// To print the preorder traversal of BST
preorderTraversal(root);
return 0;
}
Java
// Java code to balance BST using DSW algorithm.
public class DayStout {
// Defining the structure for TreeNode.
static class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int val) { this.val = val; }
}
// Function to convert input BST
// to right linked list
// known as vine or backbone.
static int bstToVine(TreeNode grand)
{
int count = 0;
// Make tmp pointer to traverse
// and right flatten the given BST.
TreeNode tmp = grand.right;
// Traverse until tmp becomes NULL
while (tmp != null) {
// If left exist for node
// pointed by tmp then
// right rotate it.
if (tmp.left != null) {
TreeNode oldTmp = tmp;
tmp = tmp.left;
oldTmp.left = tmp.right;
tmp.right = oldTmp;
grand.right = tmp;
}
// If left dont exists
// add 1 to count and
// traverse further right to
// flatten remaining BST.
else {
count++;
grand = tmp;
tmp = tmp.right;
}
}
return count;
}
// Function to compress given tree
// with its root as grand.right.
static void compress(TreeNode grand, int m)
{
// Make tmp pointer to traverse
// and compress the given BST.
TreeNode tmp = grand.right;
// Traverse and left-rotate root m times
// to compress given vine form of BST.
for (int i = 0; i < m; i++) {
TreeNode oldTmp = tmp;
tmp = tmp.right;
grand.right = tmp;
oldTmp.right = tmp.left;
tmp.left = oldTmp;
grand = tmp;
tmp = tmp.right;
}
}
// Function to calculate the
// log base 2 of an integer
static public int log2(int N)
{
// calculate log2 N indirectly
// using log() method
int result = (int)(Math.log(N) / Math.log(2));
return result;
}
// Function to implement the algorithm
static TreeNode balanceBST(TreeNode root)
{
// create dummy node with value 0
TreeNode grand = new TreeNode(0);
// assign the right of dummy node as our input BST
grand.right = root;
// get the number of nodes in input BST and
// simultaneously convert it into right linked list.
int count = bstToVine(grand);
// gets the height of tree in which all levels
// are completely filled.
int h = log2(count + 1);
// get number of nodes until second last level
int m = (int)Math.pow(2, h) - 1;
// Left rotate for excess nodes at last level
compress(grand, count - m);
// Left rotation till m becomes 0
// Step is done as mentioned in algo to
// make BST balanced.
for (m = m / 2; m > 0; m /= 2) {
compress(grand, m);
}
// return the balanced tree
return grand.right;
}
// Function to print preorder traversal
// of Binary tree.
static void preorderTraversal(TreeNode root)
{
if (root == null)
return;
System.out.print(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
return;
}
// Driver code
public static void main(String[] args)
{
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.left.left = new TreeNode(2);
root.left.left.left = new TreeNode(1);
// Function call to implement
// Day-Stout-Warren algorithm
root = balanceBST(root);
// To print the preorder traversal of BST
preorderTraversal(root);
}
}
// This code is contributed by Lovely Jain
C#
// C# code to balance BST using DSW algorithm
using System;
public class GFG {
// Defining the structure for TreeNode.
class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
public TreeNode(int val)
{
this.val = val;
left = right = null;
}
}
// Function to convert input BST
// to right linked list
// known as vine or backbone.
static int bstToVine(TreeNode grand)
{
int count = 0;
// Make tmp pointer to traverse
// and right flatten the given BST.
TreeNode tmp = grand.right;
// Traverse until tmp becomes NULL
while (tmp != null) {
// If left exist for node
// pointed by tmp then
// right rotate it.
if (tmp.left != null) {
TreeNode oldTmp = tmp;
tmp = tmp.left;
oldTmp.left = tmp.right;
tmp.right = oldTmp;
grand.right = tmp;
}
// If left dont exists
// add 1 to count and
// traverse further right to
// flatten remaining BST.
else {
count++;
grand = tmp;
tmp = tmp.right;
}
}
return count;
}
// Function to compress given tree
// with its root as grand.right.
static void compress(TreeNode grand, int m)
{
// Make tmp pointer to traverse
// and compress the given BST.
TreeNode tmp = grand.right;
// Traverse and left-rotate root m times
// to compress given vine form of BST.
for (int i = 0; i < m; i++) {
TreeNode oldTmp = tmp;
tmp = tmp.right;
grand.right = tmp;
oldTmp.right = tmp.left;
tmp.left = oldTmp;
grand = tmp;
tmp = tmp.right;
}
}
// Function to calculate the
// log base 2 of an integer
static public int log2(int N)
{
// calculate log2 N indirectly
// using log() method
int result = (int)(Math.Log(N) / Math.Log(2));
return result;
}
// Function to implement the algorithm
static TreeNode balanceBST(TreeNode root)
{
// create dummy node with value 0
TreeNode grand = new TreeNode(0);
// assign the right of dummy node as our input BST
grand.right = root;
// get the number of nodes in input BST and
// simultaneously convert it into right linked list.
int count = bstToVine(grand);
// gets the height of tree in which all levels
// are completely filled.
int h = log2(count + 1);
// get number of nodes until second last level
int m = (int)Math.Pow(2, h) - 1;
// Left rotate for excess nodes at last level
compress(grand, count - m);
// Left rotation till m becomes 0
// Step is done as mentioned in algo to
// make BST balanced.
for (m = m / 2; m > 0; m /= 2) {
compress(grand, m);
}
// return the balanced tree
return grand.right;
}
// Function to print preorder traversal
// of Binary tree.
static void preorderTraversal(TreeNode root)
{
if (root == null)
return;
Console.Write(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
return;
}
static public void Main()
{
// Code
TreeNode root = new TreeNode(10);
root.left = new TreeNode(5);
root.left.left = new TreeNode(2);
root.left.left.left = new TreeNode(1);
// Function call to implement
// Day-Stout-Warren algorithm
root = balanceBST(root);
// To print the preorder traversal of BST
preorderTraversal(root);
}
}
// This code is contributed by lokesh(lokeshmvs21).
Javascript
<script>
// Javascript code to balance BST using DSW algorithm.
// Defining the structure for TreeNode.
class TreeNode {
constructor(x = 0, left = null, right = null){
this.val = x
this.left = left
this.right = right
}
}
// Function to convert input BST
// to right linked list
// known as vine or backbone.
function bstToVine(grand) {
let count = 0;
// Make tmp pointer to traverse
// and right flatten the given BST.
let tmp = grand.right;
// Traverse until tmp becomes NULL
while (tmp) {
// If left exist for node
// pointed by tmp then
// right rotate it.
if (tmp.left) {
let oldTmp = tmp;
tmp = tmp.left;
oldTmp.left = tmp.right;
tmp.right = oldTmp;
grand.right = tmp;
}
// If left dont exists
// add 1 to count and
// traverse further right to
// flatten remaining BST.
else {
count++;
grand = tmp;
tmp = tmp.right;
}
}
return count;
}
// Function to compress given tree
// with its root as grand.right.
function compress(grand, m) {
// Make tmp pointer to traverse
// and compress the given BST.
let tmp = grand.right;
// Traverse and left-rotate root m times
// to compress given vine form of BST.
for (let i = 0; i < m; i++) {
let oldTmp = tmp;
tmp = tmp.right;
grand.right = tmp;
oldTmp.right = tmp.left;
tmp.left = oldTmp;
grand = tmp;
tmp = tmp.right;
}
}
// Function to implement the algorithm
function balanceBST(root) {
// create dummy node with value 0
let grand = new TreeNode(0);
// assign the right of dummy node as our input BST
grand.right = root;
// get the number of nodes in input BST and
// simultaneously convert it into right linked list.
let count = bstToVine(grand);
// gets the height of tree in which all levels
// are completely filled.
let h = Math.log2(count + 1);
// get number of nodes until second last level
let m = Math.pow(2, h) - 1;
// Left rotate for excess nodes at last level
compress(grand, count - m);
// Left rotation till m becomes 0
// Step is done as mentioned in algo to
// make BST balanced.
for (m = Math.floor(m / 2); m > 0; m = Math.floor(m / 2)) {
compress(grand, m);
}
// return the balanced tree
return grand.right;
}
// Function to print preorder traversal
// of Binary tree.
function preorderTraversal(root) {
if (!root)
return;
document.write(root.val + " ");
preorderTraversal(root.left);
preorderTraversal(root.right);
return;
}
// Driver code
let root = new TreeNode(10);
root.left = new TreeNode(5);
root.left.left = new TreeNode(2);
root.left.left.left = new TreeNode(1);
// Function call to implement
// Day-Stout-Warren algorithm
root = balanceBST(root);
// To print the preorder traversal of BST
preorderTraversal(root);
// This code is contributed by saurabh_jaiswal.
</script>
Producción
5 2 1 10
Complejidad de tiempo: O(N) donde N es el número total de Nodes en el
espacio auxiliar BST: O(1)
Publicación traducida automáticamente
Artículo escrito por jayshilbuddhadev y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA