為什么刪除二叉排序樹中一個結點,再重新插入上去,不一定得到原來的二叉排序樹？二進制排序樹只要求每個節(jié)點的左子級小于它，右子級大于或等于它。先看刪除操作：“先將刪除的節(jié)點與最后一個節(jié)點交換，交換后刪除最

為什么刪除二叉排序樹中一個結點,再重新插入上去,不一定得到原來的二叉排序樹？

二進制排序樹只要求每個節(jié)點的左子級小于它，右子級大于或等于它。先看刪除操作：“先將刪除的節(jié)點與最后一個節(jié)點交換，交換后刪除最后一個節(jié)點，然后重建二叉樹”，在這個過程中，如果刪除根節(jié)點左側的節(jié)點，則在與最后一個節(jié)點交換后，為了保持二叉排序樹的特性，最后一個節(jié)點會逐漸向上移動，這很可能會改變根節(jié)點的位置。然后讓我們看看插入操作：“直接與根節(jié)點比較。如果小于根節(jié)點，插入左子樹，遞歸一次，選擇合適的節(jié)點，如果大于根節(jié)點，依此類推。所以平衡二叉樹可能不同。我建議你畫一幅圖，試著操作一下，加深對這兩種操作的理解

二叉排序樹T，對于給出的正整數x，將data域值小于等于x的結點全部刪除掉。在空白處填入正確的語句？

每個節(jié)點最多有兩個叉的樹稱為二叉樹。搜索樹和排序樹是一回事。其特點是遍歷中間階的結果是單調的。這種樹可以用于二進制搜索。平衡樹一般是一種排序樹，并添加一個點條件，即任意節(jié)點的兩個叉的深度幾乎相同（例如，差值的絕對值小于一個常數，或者一個叉的深度不能是另一個叉的兩倍）。這樣的樹可以保證二進制搜索的任何元素都是O（logn），并且具有插入或刪除元素都是O（logn）的屬性。