Tìm các nút được hoán đổi trong BST

Question

Tôi đang cố viết một chương trình có thể phát hiện và in hai nút trong BST đã được hoán đổi.

Trong một cây ba cấp, tôi đã đạt đến gần giải pháp bằng cách sử dụng phương pháp này.

If (!AllSubTreeAreValid()) 
{ 
//Nodes swapped on same side of main root node 
} 
else 
{ 
    int max = getMax(root->left); 
    int min = getMin(root->right); 
    if(max > root->data || min < root->data) 
    { 
    //Nodes swapped on different sides of main root node 
    //Print max and min values 

    } 
else 
{ 
//No node swappped 
} 
} 

//Helper functions 
int GetMaxEle(TreeNode* tree) 
{ 
    while(tree->right!=NULL) 
    { 
     tree=tree->right; 
    } 
    return tree->info; 
} 

int GetMinEle(TreeNode* tree) 
{ 
    while(tree->left!=NULL) 
    { 
     tree=tree->left; 
    } 
    return tree->info; 
} 

nhưng cách tiếp cận trên không thành công khi tôi cố gắng thử nghiệm với bốn cấp độ cây.

   20 

     15   30 

    10 17  25  33 

9 16 12 18 22 26 31 34 

Ở trong nút gốc bên phải của 15, 12 vẫn lớn hơn (vi phạm).

Ở trong nhánh trái của nút gốc 15, 16 vẫn lớn hơn (vi phạm).

Vì vậy, 16, 12 là các phần tử được hoán đổi trong BST ở trên. Làm thế nào để tôi tìm thấy chúng thông qua chương trình?

Answer 1

Một cách để suy nghĩ về vấn đề này là sử dụng thực tế là một inorder đi bộ của cây sẽ sản xuất tất cả các yếu tố theo thứ tự sắp xếp. Nếu bạn có thể phát hiện sai lệch từ thứ tự được sắp xếp trong khi đi bộ này, bạn có thể tìm cách xác định hai phần tử sai vị trí.

Hãy xem cách thực hiện điều này cho một mảng được sắp xếp đơn giản trước tiên, sau đó sẽ sử dụng thuật toán của chúng tôi để tạo thứ gì đó hoạt động trên cây. Trực giác, nếu chúng ta bắt đầu với một mảng được sắp xếp và sau đó hoán đổi hai phần tử (không bằng nhau!), Chúng ta sẽ kết thúc với một số phần tử trong mảng bị mất vị trí. Ví dụ, với các mảng

1 2 3 4 5 

Nếu chúng ta trao đổi 2 và 4, chúng ta kết thúc với mảng này:

1 4 3 2 5 

Làm thế nào chúng ta sẽ phát hiện rằng 2 và 4 đã được hoán đổi ở đây? Vâng, vì 4 là lớn hơn trong hai phần tử và được hoán đổi xuống, nên lớn hơn cả hai phần tử xung quanh nó. Tương tự như vậy, bởi vì 2 đã được hoán đổi, nó phải nhỏ hơn cả hai yếu tố xung quanh nó. Từ đó, chúng ta có thể kết luận rằng 2 và 4 được đổi chỗ.

Tuy nhiên, điều này không phải lúc nào cũng hoạt động chính xác. Ví dụ: giả sử chúng tôi trao đổi 1 và 4:

4 2 3 1 5 

Ở đây, cả 2 và 1 đều nhỏ hơn các thành phần lân cận và cả 4 và 3 đều lớn hơn các phần tử lân cận.Từ điều này chúng ta có thể nói rằng hai trong số bốn cách này đã được đổi chỗ, nhưng không rõ chúng ta nên trao đổi cái gì. Tuy nhiên, nếu chúng ta lấy giá trị lớn nhất và nhỏ nhất của các giá trị này (lần lượt là 1 và 4), chúng ta sẽ nhận được cặp đã được hoán đổi.

Tổng quát hơn, để tìm các yếu tố đã được hoán đổi trong trình tự, bạn muốn tìm

• tối đa địa phương lớn nhất trong mảng.
• Tối thiểu địa phương nhỏ nhất trong mảng.

Hai yếu tố này không đúng chỗ và cần được hoán đổi.

Bây giờ, hãy suy nghĩ về cách áp dụng điều này cho cây. Vì một bước đi sắp xếp của cây sẽ tạo ra trình tự sắp xếp với hai phần tử ra khỏi trật tự, một lựa chọn là đi bộ cây, ghi lại chuỗi thứ tự các phần tử chúng ta đã tìm thấy, sau đó sử dụng thuật toán trên. Ví dụ, hãy xem xét BST ban đầu của bạn:

   20 
     /  \ 
     15    30 
    / \  / \ 
    10 17  25  33 
/| /\ /\ | \ 
9 16 12 18 22 26 31 34 

Nếu chúng ta linearize này vào một mảng, chúng tôi nhận

9 10 16 15 12 17 18 20 22 25 26 30 31 33 34 

ý rằng 16 là lớn hơn yếu tố xung quanh nó và rằng 12 là ít hơn các sản phẩm. Điều này ngay lập tức cho chúng ta biết rằng 12 và 16 đã được đổi chỗ. Một thuật toán đơn giản để giải quyết vấn đề này, do đó, sẽ làm một bước đi trật tự của cây để tuyến tính hóa nó thành một chuỗi như là vector hoặc deque, sau đó quét chuỗi đó để tìm tối đa địa phương lớn nhất và nhỏ nhất tối thiểu địa phương. Điều này sẽ chạy trong thời gian O (n), sử dụng không gian O (n). Thuật toán hiệu quả hơn nhưng không gian hiệu quả hơn sẽ chỉ theo dõi ba nút tại một thời điểm - nút hiện tại, nút tiền nhiệm của nó và người kế nhiệm - làm giảm mức sử dụng bộ nhớ thành O (1).

Hy vọng điều này sẽ hữu ích!

Answer 2

Tôi đoán et getMin bạn GetMax làm việc witht các giả thuyết rằng cây là một BST, vì vậy

T getMax(tree) { 
    return tree -> right == null 
    ? tree -> value 
    : getMax(tree -> right); 
} 

(hoặc mã tương đương với một vòng lặp). Nếu có, mã của bạn sẽ kiểm tra tối đa ba giá trị trong cây. Ngay cả khi getMax và getMin đi qua cây đầy đủ để có được giá trị tối đa/phút thực tế, bạn vẫn sẽ dựa vào thử nghiệm của mình chỉ với hai so sánh. Nếu bạn muốn kiểm tra xem cây của bạn có đáp ứng thuộc tính BST hay không, rõ ràng là bạn phải kiểm tra tất cả các giá trị. Nó đủ để so sánh mỗi nút với cha mẹ của nó.

void CheckIsBst(Tree *tree) { 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left); 
    } 
    // same with -> right, reversing <to> in the test 
} 

Chỉnh sửa: không đúng, hãy xem nhận xét. Tôi tin rằng điều này là ok.

void checkIsBst(Tree *Tree, Tree *lowerBound, Tree *upperBound) { 
    if(lowerBound!= null && lowerBound -> value > tree -> Value) { 
    //violation 
    } 
    // same for upper bound, check with < 
    if (tree -> left != null) { 
    if (tree -> left -> value > tree -> value) { 
     // print violation 
    } 
    CheckIsBst(tree -> left, lowerBound, tree); 
    } 
    // same for right, reversing comparison 
    // setting lowerBound to tree instead of upperBound 
} 

Gọi từ gốc với giới hạn vô

Answer 3

duyệt cây được thực hiện bởi templatetypedef hoạt động nếu bạn chắc chắn chỉ có một lần hoán đổi. Nếu không, tôi đề xuất giải pháp dựa trên mã ban đầu của bạn:

int GetMax(TreeNode* tree) { 
    int max_right, max_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     max_left = GetMax(tree->left); 
     if (max_left > ret) 
      ret = max_left; 
    } 
    if (tree->right != NULL) { 
     max_right = GetMax(tree->right); 
     if (max_right > ret) 
      ret = max_right; 
    } 

    return ret; 
} 

int GetMin(TreeNode* tree) { 
    int min_right, min_left, ret; 

    ret = tree->data; 
    if (tree->left != NULL) { 
     min_left = GetMin(tree->left); 
     if (min_left < ret) 
      ret = min_left; 
    } 
    if (tree->right != NULL) { 
     min_right = GetMin(tree->right); 
     if (min_right < ret) 
      ret = min_right; 
    } 

    return ret; 
} 

void print_violations(TreeNode* tree) { 
    if ((tree->left != NULL) && (tree->right != NULL)) { 
     int max_left = GetMax(tree->left); 
     int min_right = GetMin(tree->right); 
     if (max_left > tree->data && min_right < tree->data) { 
      printf("Need to swap %d with %d\n", max_left, min_right); 
     } 
    } 
    if (tree->left != NULL) 
     print_violations(tree->left); 
    if (tree->right != NULL) 
     print_violations(tree->right); 
} 

Nó chậm hơn nhưng in tất cả các hoán đổi mà nó nhận dạng. Có thể thay đổi để in tất cả các vi phạm (ví dụ: nếu vi phạm in (max_left> cây-> dữ liệu)). Bạn có thể cải thiện hiệu suất nếu bạn có thể thêm hai trường vào TreeNode với giá trị tối đa và tối thiểu cho cây con đó.