Ответ: да и нет.
B-деревья не должны выполнять вращения, потому что они имеют некоторый слабины, сколько разных ключей они могут упаковать в узел. Когда вы добавляете все больше и больше ключей в B-дерево, вы можете избежать того, что дерево становится односторонним, поглощая эти ключи в самих узлах.
Двоичные деревья не имеют этой роскоши. Если вы вставляете ключ в двоичное дерево, он увеличит высоту какой-либо ветки в этом дереве на 1 во всех случаях, потому что этот ключ должен перейти в свой собственный узел. Вращения борются с общим ростом дерева, гарантируя, что если некоторые ветви растут слишком сильно, эта высота перетасовывается в остальную часть дерева.
Большинство сбалансированных BST имеют своего рода стратегию балансировки, которая включает в себя вращение, но не все. Одним из примечательных примеров стратегии, которая непосредственно не связана с поворотами, является scapegoat tree, которая перебалансирует, вырывая огромные поддеревья из главного дерева, оптимально перестраивая их, а затем склеивая поддерево обратно в основное дерево. Этот подход не технически включает в себя любые вращения и является довольно чистым способом реализации сбалансированного дерева.
Это говорит о том, что наиболее эффективные по площади реализации деревьев козла отпущения действительно используют вращения для преобразования несбалансированного дерева в идеально сбалансированный. У вас не есть, чтобы использовать вращения, чтобы сделать это, хотя, если пространство короткое, это, вероятно, лучший способ сделать это.
Надеюсь, это поможет!
Дерево B не является двоичным деревом. – amit
(В примере на geeksforgeeks (второй [ЗДЕСЬ] (http://www.geeksforgeeks.org/b-tree-set-1-insert-2/) диаграмма «после вставки 90» кажется удачной.) Существует [2-3 дерева] (http://en.wikipedia.org/wiki/2%E2%80%933_tree) - посмотрите на удаления там и на деревьях B тоже. – greybeard
@greybeard Они не бинарные деревья. – amit