search

OccupyMars2025 / Introduction-to-Algorithms-4th-Edition

Time is Money, Efficiency is Life
MIT License
1 stars 0 forks source link

[solved][debug][ Exercise 12.3-6] in python, tree_delete method have bugs #10

Closed OccupyMars2025 closed 3 months ago

OccupyMars2025 commented 4 months ago 
After deleting 61
Inorder traversal of the BST:
1 4 18 51 68 75 76 77 82 92 
1,succ:4 4,succ:68 18,succ:51 51,succ:68 68,succ:75 75,succ:76 76,succ:77 77,succ:82 82,succ:92 92,succ:None 
1 4 68 75 76 77 82 92 
Traceback (most recent call last):
  File "/home/occupymars2025/Downloads/Introduction-to-Algorithms-4th-Edition/my_implementation/Chapter_12_Binary_Search_Tree/Exercises-12.3/12.3-6-code/bst.py", line 314, in <module>
    test()
  File "/home/occupymars2025/Downloads/Introduction-to-Algorithms-4th-Edition/my_implementation/Chapter_12_Binary_Search_Tree/Exercises-12.3/12.3-6-code/bst.py", line 310, in test
    bst.test_the_structure()
  File "/home/occupymars2025/Downloads/Introduction-to-Algorithms-4th-Edition/my_implementation/Chapter_12_Binary_Search_Tree/Exercises-12.3/12.3-6-code/bst.py", line 283, in test_the_structure
    assert len(collected_inorder_list) == len(collected_inorder_list_v2)
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError
make: *** [Makefile:4: python] Error 1
occupymars2025@occupymars2025:~/Downloads/Introduction-to-Algorithms-4th-Edition/my_implementation/Chapter_12_Binary_Search_Tree/Exercises-12.3/12.3-6-code$ 
(eog:12324): EOG-CRITICAL **: 09:00:20.595: eog_image_get_file: assertion 'EOG_IS_IMAGE (img)' failed

(eog:12324): GLib-GIO-CRITICAL **: 09:00:20.595: g_file_equal: assertion 'G_IS_FILE (file1)' failed
^C
occupymars2025@occupymars2025:~/Downloads/Introduction-to-Algorithms-4th-Edition/my_implementation/Chapter_12_Binary_Search_Tree/Exercises-12.3/12.3-6-code$

I get the structure of the binary search tree when the bugs occur:

before deleting 61

image

after deleting 61

image

compare them

image

OccupyMars2025 commented 4 months ago

Solution: https://github.com/OccupyMars2025/Introduction-to-Algorithms-4th-Edition/commit/190b1269aa9dd4c88b890919335eac24da5daa89

image

In case (c) and (d), after excuting transplant(q, z, y), predecessor(z_subtree).succ becomes y, but actually, it doesn't have to be changed, so we have to restore its original value

OccupyMars2025 commented 4 months ago

but I still get the following errors, since it seems to have no bad influences for now, I just ignore them


(eog:18668): EOG-CRITICAL **: 10:21:19.276: eog_image_get_file: assertion 'EOG_IS_IMAGE (img)' failed

(eog:18668): GLib-GIO-CRITICAL **: 10:21:19.276: g_file_equal: assertion 'G_IS_FILE (file1)' failed