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

為什么刪除二叉排序樹(shù)中一個(gè)結(jié)點(diǎn),再重新插入上去,不一定得到原來(lái)的二叉排序樹(shù)？

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

二叉排序樹(shù)T，對(duì)于給出的正整數(shù)x，將data域值小于等于x的結(jié)點(diǎn)全部刪除掉。在空白處填入正確的語(yǔ)句？

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