ตรวจสอบ Array แทน BST ความสูง n ระดับได้หรือไม่ใน C++

เรามี Array A ต้องการตรวจสอบว่าแทน BST ความสูง n ระดับได้หรือไม่ เนื่องจากระดับคือ n เราสามารถสร้าง Tree ได้ดังนี้: สมมติค่าคือ k ค่ามากกว่า k ไปขวา น้อยกว่า k ไปซ้าย ตัวอย่าง 2 Lists: {50, 20, 9, 25, 10} และ {50, 30, 20, 25, 10}

List แรกไม่ถูกต้อง List ที่สองถูกต้อง

วิธีตรวจสอบแบบ Array-based:

• ตัวแปร max = infinity (ขีดจำกัดบนของ Left Subtree) min = -infinity (ขีดจำกัดล่างของ Right Subtree)
• สำหรับแต่ละ Element ในช่วง arr[i] ถึง arr[n-1]:
  • ถ้า arr[i] > arr[i-1] และ arr[i] > min และ arr[i] < max อัปเดต min := arr[i-1]
  • มิฉะนั้นถ้า arr[i] < arr[i-1] และ arr[i] > min และ arr[i] < max อัปเดต max := arr[i-1]
  • ถ้าไม่ผ่านเงื่อนไขใดๆ แสดงว่า Element จะถูก Insert ใน Level ใหม่ จึง break

ตัวอย่างโค้ด C++

#include <iostream>
using namespace std;

bool canMakeBSTifHeightN(int arr[], int n) {
    int min = INT_MIN;
    int max = INT_MAX;
    for(int i = 1; i < n; i++) {
        if (arr[i] > arr[i - 1] && arr[i] > min && arr[i] < max) {
            min = arr[i - 1];
        } else if (arr[i] < arr[i - 1] && arr[i] > min && arr[i] < max) {
            max = arr[i - 1];
        } else {
            return true;
        }
    }
    return false;
}

int main() {
    int elements[] = {50, 30, 20, 25, 10};
    int n = sizeof(elements)/sizeof(elements[0]);
    if (canMakeBSTifHeightN(elements, n))
        cout << "We can make BST of height " << n;
    else
        cout << "We can not make BST of height " << n;
}

ผลลัพธ์

We can make BST of height 5