Создать сбалансированное бинарное дерево поиска из отсортированного связанного списка

Question

Какой лучший способ создать сбалансированное двоичное дерево поиска из отсортированного односвязного списка?

Answer 1

Как насчет создания узлов снизу вверх?

Сложность времени этого решения O (N). Подробное объяснение в моем блоге:

http://www.leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

Два обхода связанного списка - это все, что нам нужно. Сначала выполните обход длины списка (который затем передается в качестве параметра n в функцию), затем создайте узлы по порядку списка.

BinaryTree* sortedListToBST(ListNode *& list, int start, int end) {
  if (start > end) return NULL;
  // same as (start+end)/2, avoids overflow
  int mid = start + (end - start) / 2;
  BinaryTree *leftChild = sortedListToBST(list, start, mid-1);
  BinaryTree *parent = new BinaryTree(list->data);
  parent->left = leftChild;
  list = list->next;
  parent->right = sortedListToBST(list, mid+1, end);
  return parent;
}

BinaryTree* sortedListToBST(ListNode *head, int n) {
  return sortedListToBST(head, 0, n-1);
}

Answer 2

Вы не можете работать лучше, чем линейное время, так как вам нужно, по крайней мере, прочитать все элементы списка, так что вы можете также скопировать список в массив (линейное время) и затем эффективно построить дерево вобычным способом, т. е. если бы у вас был список [9,12,18,23,24,51,84], то вы бы начали с 23 корня, с детьми 12 и 51, тогда 9 и 18 стали детьми 12и 24 и 84 становятся дочерними для 51. В целом, должно быть O (n), если вы все сделаете правильно.

Фактический алгоритм, для чего он стоит, это «принять средний элемент списка в качествеroot, и рекурсивно собирать BST для подсписков слева и справа от среднего элемента и прикреплять их под корнем ".

Answer 3

Это реализация Python:

def sll_to_bbst(sll, start, end):
    """Build a balanced binary search tree from sorted linked list.

    This assumes that you have a class BinarySearchTree, with properties
    'l_child' and 'r_child'.

    Params:
        sll: sorted linked list, any data structure with 'popleft()' method,
            which removes and returns the leftmost element of the list. The
            easiest thing to do is to use 'collections.deque' for the sorted
            list.
        start: int, start index, on initial call set to 0
        end: int, on initial call should be set to len(sll)

    Returns:
        A balanced instance of BinarySearchTree

    This is a python implementation of solution found here: 
    http://leetcode.com/2010/11/convert-sorted-list-to-balanced-binary.html

    """

    if start >= end:
        return None

    middle = (start + end) // 2
    l_child = sll_to_bbst(sll, start, middle)
    root = BinarySearchTree(sll.popleft())
    root.l_child = l_child
    root.r_child = sll_to_bbst(sll, middle+1, end)

    return root

Answer 4

Вопрос с подвохом!

Лучший способ - использовать STL и воспользоваться тем фактом, что отсортированный ассоциативный контейнер ADT, набор которого является реализацией, требует вставки отсортированных диапазонов с амортизированным линейным временем. Любой проходимый набор основных структур данных для любого языка должен предлагать аналогичную гарантию. Чтобы получить реальный ответ, см. Довольно умные решения, предоставленные другими.

---

Что это? Я должен предложить что-то полезное?

Hum ...

Как насчет этого?

Наименьшее возможное значимое дерево в сбалансированном бинарном дереве - это 3 узла. Родитель и двое детей. Самым первым экземпляром такого дерева являются первые три элемента. Ребенок-родитель-ребенок. Давайте теперь представим это как один узел. Хорошо, у нас больше нет дерева. Но мы знаем, что нам нужна форма Child-parent-Child.
Сделано на мгновение нашим воображением, мы хотим сохранить указатель на родителя в этом начальном триумвирате. Но это однозначно!
Мы хотим иметь четыре указателя, которые я назову A, B, C и D. Итак, мы переместим A в 1, установим B равным A и переместим его на единицу. Установите C равным B, и продвиньте это два. Узел под B уже указывает на своего правого потомка. Мы строим наше первоначальное дерево. Мы оставляем B у родителя первого дерева. Си сидит в узле, который будет иметь два наших минимальных дерева в качестве детей. Установите A равным C и продвиньте его на единицу. Установите D равным A и продвиньте его на единицу. Теперь мы можем построить наше следующее минимальное дерево. D указывает на корень этого дерева, B указывает на корень другого, а C указывает на ... новый корень, из которого мы будем вешать два наших минимальных дерева.

Как насчет картинок?

[A][B][-][C]  

С нашим изображением минимального дерева в качестве узла ...

[B = Tree][C][A][D][-]

А потом

[Tree A][C][Tree B]

За исключением того, что у нас есть проблема. Узел два после D - наш следующий корень.

[B = Tree A][C][A][D][-][Roooooot?!]  

Нам было бы намного проще, если бы мы могли просто поддерживать указатель на него, а не на него и C. Получается, поскольку мы знаем, что это будет указывать на C, мы можем пойти дальше и начать строить узел в двоичное дерево, которое будет содержать его, и как часть этого мы можем ввести C в него как левый узел. Как мы можем сделать это элегантно?

Установить указатель узла под C на узел под B.
Это обман во всех смыслах этого слова, но, используя этот трюк, мы освобождаем B.
Кроме того, вы можете быть в здравом уме, и на самом деле начать строить структуру узла. В конце концов, вы действительно не можете повторно использовать узлы из SLL, они, вероятно, являются структурами POD.

Так что теперь ...

[TreeA]<-[C][A][D][-][B]  
[TreeA]<-[C]->[TreeB][B] 

И ... Подожди секунду. Мы можем использовать этот же трюк, чтобы освободить C, если мы просто будем думать о нем как об одном узле вместо дерева. Ведь в конце концов, это всего лишь один узел.

[TreeC]<-[B][A][D][-][C]  

Мы можем обобщить наши уловки.

[TreeC]<-[B][TreeD]<-[C][-]<-[D][-][A]    
[TreeC]<-[B][TreeD]<-[C]->[TreeE][A]  
[TreeC]<-[B]->[TreeF][A]  
[TreeG]<-[A][B][C][-][D]
[TreeG]<-[A][-]<-[C][-][D]  
[TreeG]<-[A][TreeH]<-[D][B][C][-]  
[TreeG]<-[A][TreeH]<-[D][-]<-[C][-][B]  
[TreeG]<-[A][TreeJ]<-[B][-]<-[C][-][D]  
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]      
[TreeG]<-[A][TreeJ]<-[B][TreeK]<-[D][-]<-[C][-]  

Мы пропустили важный шаг!

[TreeG]<-[A]->([TreeJ]<-[B]->([TreeK]<-[D][-]<-[C][-]))  

Становится:

[TreeG]<-[A]->[TreeL->([TreeK]<-[D][-]<-[C][-])][B]    
[TreeG]<-[A]->[TreeL->([TreeK]<-[D]->[TreeM])][B]  
[TreeG]<-[A]->[TreeL->[TreeN]][B]  
[TreeG]<-[A]->[TreeO][B]  
[TreeP]<-[B]  

Очевидно, что алгоритм может быть значительно очищен, но я подумал, что было бы интересно продемонстрировать, как можно оптимизировать свою работу путем итеративной разработки алгоритма. Я думаю, что такой процесс - это то, что хороший работодатель должен искать больше всего на свете.

Суть в том, что каждый раз, когда мы достигаем следующей средней точки, которая, как мы знаем, является будущим родителем, мы знаем, что его левое поддерево уже закончено.Другой трюк заключается в том, что мы закончили с узлом, когда у него есть два дочерних элемента и что-то указывает на него, даже если все поддеревья не завершены.Используя это, мы можем получить то, что, я уверен, является линейным решением по времени, так как каждый элемент касается только 4 раза.Проблема в том, что это зависит от получения списка, который сформирует действительно сбалансированное двоичное дерево поиска.Другими словами, существуют некоторые скрытые ограничения, которые могут сделать это решение более сложным для применения или невозможным.Например, если у вас нечетное количество элементов или много неуникальных значений, это приводит к довольно глупому дереву.

Соображения:

• Сделать элемент уникальным.
• Вставить фиктивный элемент в конце, если число узлов нечетное.
• Пойте с тоской для более наивной реализации.
• Используйте деку, чтобы сохранить корни завершенных поддеревьев и средних точек, вместо того, чтобы копаться со вторым трюком.

Answer 5

Лучше всего не только об асимптотическом времени выполнения.Сортированный связанный список содержит всю информацию, необходимую для непосредственного создания двоичного дерева, и я думаю, что это, вероятно, то, что они ищут

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

в коде псевдо

read three elements, make a node from them, mark as level 1, push on stack
loop
    read three elemeents and make a node of them
    mark as level 1
    push on stack
    loop while top two enties on stack have same level (n)
         make node of top two entries, mark as level n + 1, push on stack
while elements remain in list

(с небольшим изменением для того, когда меньшеосталось три элемента или несбалансированное дерево в любой точке)

РЕДАКТИРОВАТЬ:

В любой точке в стеке находится левый узел высоты N.Следующим шагом является чтение одного элемента, затем чтение и построение другого узла высоты N в стеке.Чтобы построить узел с высотой N, создайте и поместите в стек узел с высотой N -1, затем прочитайте элемент, создайте в стеке еще один узел с высотой N-1 - это рекурсивный вызов.

На самом деле это означает, что алгоритм (даже измененный) не будет создавать сбалансированное дерево.Если имеется 2N + 1 узел, он создаст дерево со значениями 2N-1 слева и 1 справа.

Так что я думаю, что ответ @ sgolodetz будет лучше, если только я не смогу придумать способ сбалансировать дерево по мере его построения.

Answer 6

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

typedef struct Node{
     struct Node *left;
     int info;
     struct Node  *right;
}Node_t;

Node_t* Bin(int low, int high) {

     Node_t* node = NULL;
     int mid = 0;

     if(low <= high) {
         mid = (low+high)/2;
         node = CreateNode(a[mid]);
         printf("DEBUG: creating node for %d\n", a[mid]);

        if(node->left == NULL) {
            node->left = Bin(low, mid-1);
        }

        if(node->right == NULL) {
            node->right = Bin(mid+1, high);
        }

        return node;
    }//if(low <=high)
    else {
        return NULL;
    }
}//Bin(low,high)


Node_t* CreateNode(int info) {

    Node_t* node = malloc(sizeof(Node_t));
    memset(node, 0, sizeof(Node_t));
    node->info = info;
    node->left = NULL;
    node->right = NULL;

    return node;

}//CreateNode(info)

// call function for an array example: 6 7 8 9 10 11 12, it gets you desired 
// result

 Bin(0,6); 

HTH Кто-нибудь ..

Answer 7

Если вы знаете, сколько узлов в связанном списке, вы можете сделать это следующим образом:

// Gives path to subtree being built.  If branch[N] is false, branch
// less from the node at depth N, if true branch greater.
bool branch[max depth];

// If rem[N] is true, then for the current subtree at depth N, it's
// greater subtree has one more node than it's less subtree.
bool rem[max depth];

// Depth of root node of current subtree.
unsigned depth = 0;

// Number of nodes in current subtree.
unsigned num_sub = Number of nodes in linked list;

// The algorithm relies on a stack of nodes whose less subtree has
// been built, but whose right subtree has not yet been built.  The
// stack is implemented as linked list.  The nodes are linked
// together by having the "greater" handle of a node set to the
// next node in the list.  "less_parent" is the handle of the first
// node in the list.
Node *less_parent = nullptr;

// h is root of current subtree, child is one of its children.
Node *h, *child;

Node *p = head of the sorted linked list of nodes;

LOOP // loop unconditionally

    LOOP WHILE (num_sub > 2)
        // Subtract one for root of subtree.
        num_sub = num_sub - 1;

        rem[depth] = !!(num_sub & 1); // true if num_sub is an odd number
        branch[depth] = false;
        depth = depth + 1;
        num_sub = num_sub / 2;
    END LOOP

    IF (num_sub == 2)
        // Build a subtree with two nodes, slanting to greater.
        // I arbitrarily chose to always have the extra node in the
        // greater subtree when there is an odd number of nodes to
        // split between the two subtrees.

        h = p;
        p = the node after p in the linked list;
        child = p;
        p = the node after p in the linked list;
        make h and p into a two-element AVL tree;
    ELSE  // num_sub == 1

        // Build a subtree with one node.

        h = p;
        p = the next node in the linked list;
        make h into a leaf node;
    END IF

    LOOP WHILE (depth > 0)
        depth = depth - 1;
        IF (not branch[depth])
            // We've completed a less subtree, exit while loop.
            EXIT LOOP;
        END IF

        // We've completed a greater subtree, so attach it to
        // its parent (that is less than it).  We pop the parent
        // off the stack of less parents.
        child = h;
        h = less_parent;
        less_parent = h->greater_child;
        h->greater_child = child;
        num_sub = 2 * (num_sub - rem[depth]) + rem[depth] + 1;
        IF (num_sub & (num_sub - 1))
          // num_sub is not a power of 2
          h->balance_factor = 0;
        ELSE
          // num_sub is a power of 2
          h->balance_factor = 1;
        END IF
    END LOOP

    IF (num_sub == number of node in original linked list)
        // We've completed the full tree, exit outer unconditional loop
        EXIT LOOP;
    END IF

    // The subtree we've completed is the less subtree of the
    // next node in the sequence.

    child = h;
    h = p;
    p = the next node in the linked list;
    h->less_child = child;

    // Put h onto the stack of less parents.
    h->greater_child = less_parent;
    less_parent = h;

    // Proceed to creating greater than subtree of h.
    branch[depth] = true;
    num_sub = num_sub + rem[depth];
    depth = depth + 1;

END LOOP

// h now points to the root of the completed AVL tree.

Для кодирования этого в C ++, смотрите функцию-член сборки (в настоящее время в строке 361) в https://github.com/wkaras/C-plus-plus-intrusive-container-templates/blob/master/avl_tree.h. На самом деле это более общий шаблон, использующий любой прямой итератор, а не связанный список.

Answer 8

Немного улучшенная реализация из @ 1337c0d3r в моем блоге .

// create a balanced BST using @len elements starting from @head & move @head forward by @len
TreeNode *sortedListToBSTHelper(ListNode *&head, int len) {
    if (0 == len)   return NULL;

    auto left = sortedListToBSTHelper(head, len / 2);
    auto root = new TreeNode(head->val);
    root->left = left;
    head = head->next;
    root->right = sortedListToBSTHelper(head, (len - 1) / 2);
    return root;
}

TreeNode *sortedListToBST(ListNode *head) {
    int n = length(head);
    return sortedListToBSTHelper(head, n);
}

Answer 9

Надеюсь, подробное объяснение этого поста поможет: http://preparefortechinterview.blogspot.com/2013/10/planting-trees_1.html

Answer 10

Подобно @Stuart Golodetz и @Jake Kurzer, важно то, что список уже отсортирован.

В ответе @ Stuart массив, который он представил, является структурой вспомогательных данных для BST.Например, операция поиска должна была бы просто выполнить вычисления массива индекса для обхода дерева.Выращивание массива и удаление элементов было бы более сложной задачей, поэтому я бы предпочел векторную или другую структуру данных с постоянным поиском.

@ Ответ Джейка также использует этот факт, но, к сожалению, требует, чтобы вы просмотрели список, чтобы найтикаждый раз делать операцию get (index).Но не требует дополнительного использования памяти.

Если интервьюер не особо упомянул, что они хотят представить объектную структуру дерева, я бы использовал ответ @ Stuart.

В таком вопросе, как этотвам дадут дополнительные баллы за обсуждение компромиссов и всех вариантов, которые у вас есть.