При вставке в BST первый вставленный элемент всегда является корнем дерева?

Question

Глядя на реализацию в Википедии, может показаться, что стандартный BST (несбалансированный) никогда не перестраивается во время вставки, и поэтому самый первый добавленный элемент всегда будет корневым. Это правильно? Если это так, не означает ли это, что есть вероятность того, что BST часто будет намного хуже, чем O (logN)?

Используя это как ссылку для рекурсивной вставки:

 /* Inserts the node pointed to by "newNode" into the subtree rooted at "treeNode" */
 void InsertNode(Node* &treeNode, Node *newNode)
 {
     if (treeNode == NULL)
       treeNode = newNode;
     else if (newNode->key < treeNode->key)
       InsertNode(treeNode->left, newNode);
     else
       InsertNode(treeNode->right, newNode);
 }

Answer 1

Да, всегда будет на корневом узле просто потому, что:

• это единственное место, где вы можете поместить его в пустое дерево; и
• Вы не двигаете это.

Конечно, вы можете удалить его, что приведет к тому, что другой узел станет корневым, но это не переместит оригинальный первый узел в другое место дерева.

Вырожденный случай для несбалансированного двоичного дерева представляет собой связанный список, который имеет сложность времени поиска O (n).

Answer 2

Да, несбалансированные BST могут быть плохими. Фактически, если вы добавляете отсортированные данные в BST, вы можете быстро выродить свое дерево до производительности с одним связанным списком, для которой вставка O (n), при условии, что вставка находится в конце.

Стандартный BST в среднем будет неплохо работать, если вы имеете дело со случайными данными. Ваш худший враг отсортирован, или переверните отсортированные данные.

Вот почему вы обычно хотите использовать сбалансированный BST (просто выберите один из библиотеки вашего языка).

Answer 3

Да, поэтому существуют самобалансирующиеся BST.

Answer 4

Хорошая информация в этом ответе SO .

Answer 5

Да, порядок вставки может отрицательно влиять на форму / баланс результирующего дерева. Как вы указали, результирующий наихудший случай для дерева хуже, чем O (log (N)) и может в конечном итоге выглядеть просто как связанный список.