일반 BST를 균형 BST로 변환

난이도 중급
자주 묻는 질문 아메리칸 익스프레스 ByteDance 자본 하나 그루퍼 인텔 스플 렁크 조호 (Zoho)
이진 검색 트리 이진 트리 나무조회수 23

문제 정책

이진 검색 트리 (BST)가 주어지면 BST를 균형 이진 검색 트리로 변환하는 알고리즘을 작성합니다. 균형 잡힌 이진 검색 트리는 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 1보다 작거나 같은 이진 검색 트리 일뿐입니다.

입력

일반 BST를 균형 BST로 변환

산출

일반 BST를 균형 BST로 변환

선주문 : 31 17 3 23 48 45 50 62

입력

일반 BST를 균형 BST로 변환

산출

일반 BST를 균형 BST로 변환

선주문 : 8 7

 

일반 BST를 균형 BST로 변환하는 알고리즘

한 가지 접근 방식은 주어진 이진 검색 트리를 순서대로 순회하고 요소를 자체 균형 트리에 저장하는 것입니다. AVL 트리 또는 빨강-검정 나무. 이 접근법은 그다지 효율적이지 않으며 O (N log N) 시간이 걸리고 O (N) 추가 공간을 사용합니다.

주어진 문제는 정렬 된 배열에서 균형 이진 검색 트리를 구축하는 것과 유사하며 정렬 된 배열 또는 목록을 균형 이진 검색 트리로 변환하는 방법을 알고 있습니다. 주어진 문제를 자세히 살펴보면 문제를 정렬 된 배열에서 균형 잡힌 이진 검색 트리를 구성하는 것으로 변환 할 수 있습니다.

아이디어는 순서대로 순회에서 주어진 BST를 순회하고 노드를 배열에 저장하는 것입니다. 배열에는 정렬 된 순서로 데이터가 포함됩니다. 그런 다음 정렬 된 배열을 균형 잡힌 이진 검색 트리.

1. Traverse the given binary search tree in in-order traversal and store the nodes in an array, let the array be inOrderNodes.
2. The middle element of the array forms the root of the balanced BST and all the elements to the left of middle element forms the left sub-tree and all the elements to the right of middle element forms the right sub-tree.
3. Make root's left as the result of a recursive call for step 2. For left sub-tree the start index is start in step 2 and end index is mid - 1.
4. Make root's right as the result of a recursive call for step 2. For right sub-tree the start index is mid + 1 and end index is end in step 2.
5. Return root.

복잡성 분석

시간 복잡성 = 의 위에), 우리는 전체 나무를 횡단하기 때문에 노드. 이 알고리즘에는 선형 시간 복잡도가 있습니다.
공간 복잡성 = 의 위에), 우리는 크기의 배열을 사용하기 때문에 n 이진 검색 트리의 순회 순회를 저장합니다.
여기서 n은 주어진 이진 검색 트리의 노드 수입니다.

일반 BST를 균형 BST로 변환하기위한 JAVA 코드

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.ArrayList;
class ConvertANormalBSTToBalancedBST {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;
        public Node(int data) {
            this.data = data;
        }
    }
    // function to print pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }
    // function to store the in-order traversal of a binary tree to an array
    private static void storeInOrderTraversal(Node root, ArrayList<Integer> inOrderNodes) {
        if (root != null) {
            storeInOrderTraversal(root.left, inOrderNodes);
            inOrderNodes.add(root.data);
            storeInOrderTraversal(root.right, inOrderNodes);
        }
    }
    private static Node convertSortedArrayToBalancedBST(ArrayList<Integer> inOrderNodes, int start, int end) {
        // Base Case
        if (start > end) {
            return null;
        }
        // middle element of the array forms the node
        int mid = (start + end) / 2;
        Node root = new Node(inOrderNodes.get(mid));
        // elements to the left of middle element forms left subtree
        root.left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
        // elements to the right of middle element forms right subtree
        root.right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
        // return root
        return root;
    }
    private static Node convertToBalancedBST(Node root) {
        // create an array
        ArrayList<Integer> inOrderNodes = new ArrayList<>();
        // store the in-order traversal in the array
        storeInOrderTraversal(root, inOrderNodes);
        // make balanced BST from sorted array
        return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
    }
    public static void main(String[] args) {
        // Example 1
        Node root1 = new Node(50);
        root1.left = new Node(23);
        root1.right = new Node(62);
        root1.left.left = new Node(17);
        root1.left.right = new Node(45);
        root1.left.left.left = new Node(3);
        root1.left.right.left = new Node(31);
        root1.left.right.right = new Node(48);
        root1 = convertToBalancedBST(root1);
        preOrder(root1);
        System.out.println();
        // Example 2
        Node root2 = new Node(7);
        root2.right = new Node(8);
        root2.right.right = new Node(9);
        root2 = convertToBalancedBST(root2);
        preOrder(root2);
        System.out.println();
    }
}
31 17 3 23 48 45 50 62 
8 7 9

일반 BST를 균형 BST로 변환하기위한 C ++ 코드

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print pre-order traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to store the in-order traversal of a binary tree to an array
void storeInOrderTraversal(Node *root, vector<int> &inOrderNodes) {
    if (root != NULL) {
        storeInOrderTraversal(root->left, inOrderNodes);
        inOrderNodes.push_back(root->data);
        storeInOrderTraversal(root->right, inOrderNodes);
    }
}

Node* convertSortedArrayToBalancedBST(vector<int> &inOrderNodes, int start, int end) {
    // Base Case
    if (start > end) {
        return NULL;
    }
    
    // middle element of the array forms the node
    int mid = (start + end) / 2;
    Node *root = new Node(inOrderNodes[mid]);
    
    // elements to the left of middle element forms left subtree
    root->left = convertSortedArrayToBalancedBST(inOrderNodes, start, mid - 1);
    // elements to the right of middle element forms right subtree
    root->right = convertSortedArrayToBalancedBST(inOrderNodes, mid + 1, end);
    
    // return root
    return root;
}

Node* convertToBalancedBST(Node *root) {
    // create an array
    vector<int> inOrderNodes;
    // store the in-order traversal in the array
    storeInOrderTraversal(root, inOrderNodes);
    
    // make balanced BST from sorted array
    return convertSortedArrayToBalancedBST(inOrderNodes, 0, inOrderNodes.size() - 1);
}

int main() {
    // Example 1
    Node *root1 = new Node(50);
    root1->left = new Node(23);
    root1->right = new Node(62);
    root1->left->left = new Node(17);
    root1->left->right = new Node(45);
    root1->left->left->left = new Node(3);
    root1->left->right->left = new Node(31);
    root1->left->right->right = new Node(48);
    root1 = convertToBalancedBST(root1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    Node *root2 = new Node(7);
    root2->right = new Node(8);
    root2->right->right = new Node(9);
    root2 = convertToBalancedBST(root2);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
31 17 3 23 48 45 50 62 
8 7 9
Translate »