Рубрики

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 7

Рассмотрим следующие функции левого и правого поворота, обычно используемые в саморегулирующихся BST

T1, T2 and T3 are subtrees of the tree rooted with y (on left side) 
or x (on right side)           
                y                               x
               / \     Right Rotation          /  \
              x   T3   – - – - – - – >        T1   y 
             / \       < - - - - - - -            / \
            T1  T2     Left Rotation            T2  T3

Что из следующего является самой жесткой верхней границей для операций левого и правого поворота.

(A) O (1)
(B) O (Logn)
(C) O (LogLogn)
(D) O (n)

Ответ: (А)
Объяснение: Операции вращения (вращение влево и вправо) занимают постоянное время, так как там изменяется только несколько указателей. Ниже приведены реализации C левого и правого поворота.

// Полезная функция для правого поворота поддерева с корнем у
// Смотрите диаграмму, приведенную выше.

struct node *rightRotate(struct node *y)

{

    struct node *x = y->left;

    struct node *T2 = x->right;

   

    // Выполнить вращение

    x->right = y;

    y->left = T2;

   

    // Обновление высоты

    y->height = max(height(y->left), height(y->right))+1;

    x->height = max(height(x->left), height(x->right))+1;

   

    // Возвращаем новый корень

    return x;

}

   
// Вспомогательная функция левого поворота поддерева с корнем x
// Смотрите диаграмму, приведенную выше.

struct node *leftRotate(struct node *x)

{

    struct node *y = x->right;

    struct node *T2 = y->left;

   

    // Выполнить вращение

    y->left = x;

    x->right = T2;

   

    // Обновление высоты

    x->height = max(height(x->left), height(x->right))+1;

    y->height = max(height(y->left), height(y->right))+1;

   

    // Возвращаем новый корень

    return y;

}

Тест на этот вопрос

Рекомендуемые посты:

Структуры данных | Сбалансированные деревья бинарного поиска | Вопрос 7

0.00 (0%) 0 votes