4 ms·

That's the DSW algorithm. https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm https://en.wikipedia.org/wiki/Day-Stout-Warren_algorithm

nine_k 9y ago
Pretty trivial, since you can easily find the middle of a doubly-linked list and step back. Then you simply do "find middle, use it as root, recursively build two subtrees". With a singly-linked list, it's much harder; I don't know (without googling) if a more efficient than "build and rebalance as you go" algorithm exists.
- pklausler 9y ago
  If you know the length of the initial list (and that's obviously possible in O(N)), it's all easy.
- tzs 9y ago
  You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution. You could even do this in place without increasing the size of each node at the cost of doubling the size of variables that point to nodes and slightly lowing down stepping through the list. You do this by storing the next and previous pointers for each node in the same location, xor'ed together. That doubles the size of variables that point to nodes and slows down stepping because you have to turn them into structs that store both a pointer to the node and a pointer to an adjacent node and update both of these pointers as you move through the list.
  - jandrese 9y ago
    If you're willing to burn O(n) memory on it you could just create an array of pointers to the nodes in the list and then use that to build the balanced tree. It's probably faster than iterating over the sublist every time to find the center. This assumes of course that the list is sorted. If not, you should probably sort the list first to avoid driving yourself insane. If memory is too tight to make temporary storage and the list is too big to sort and you want a perfectly balanced tree then you've got an interesting problem on your hands.
    - pklausler 9y ago
      You can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space. EDIT: demonstration: sortList [] = [] sortList [x] = [x] sortList xs = merge (sortList as) (sortList bs) where (as, bs) = split xs split [] = ([], []) split [x] = ([x], []) split (x:y:rest) = let (xs, ys) = split rest in (x:xs, y:ys) merge xs [] = xs merge [] ys = ys merge (x:xs') ys@(y:_) | x <= y = x : merge xs' ys merge xs (y:ys) = y : merge xs ys data Tree a = Empty | Node a (Tree a) (Tree a) deriving(Show) balancedTree xs = mktree (length xs) xs where mktree 0 [] = Empty mktree n xs = Node x (mktree n' less) (mktree (n - 1 - n') more) where n' = (n - 1) `div` 2 (less, (x:more)) = splitAt n' xs listToBalancedTree :: Ord a => [a] -> Tree a listToBalancedTree = balancedTree . sortList
- cbarrick 9y ago
  Lol, I like how no one is talking about DSW in the replies to the comment about DSW. > [F]ind middle, use it as root, recursively build two subtrees. That's not DSW. DSW should be way more efficient. > With a singly-linked list, it's much harder; I don't know [...] if a more efficient [...] algorithm exists. This is DSW. DSW starts with a sorted linked list--called a "vine"--and builds the tree from that, in place. The vine is a singly linked list in the sense that you only need the successor pointer (though each node obviously needs space for a predecessor pointer since it's being turned into a tree). The algorithm is O(n) time and O(1) space and is actually very elegant. Essentially, you treat the list as a completely unbalanced tree skewed to the right. Then you repeatedly apply a `compress` routine that scans down the far right path in the tree to balance it. From Wikipedia routine vine-to-tree(root, size) leaves ← size + 1 − 2^⌊log2(size + 1))⌋ compress(root, leaves) size ← size − leaves while size > 1 compress(root, ⌊size / 2⌋) size ← ⌊size / 2⌋ routine compress(root, count) scanner ← root for i ← 1 to count child ← scanner.right scanner.right ← child.right scanner ← scanner.right child.right ← scanner.left scanner.left ← child Both the naive algorithm and DSW are O(n), but the naive algorithm has a time complexity of about 2n while DSW has a time complexity of about 0.63n, assuming we start with a vine.

nine_k 9y ago

Pretty trivial, since you can easily find the middle of a doubly-linked list and step back. Then you simply do "find middle, use it as root, recursively build two subtrees". With a singly-linked list, it's much harder; I don't know (without googling) if a more efficient than "build and rebalance as you go" algorithm exists.

pklausler 9y ago
If you know the length of the initial list (and that's obviously possible in O(N)), it's all easy.
tzs 9y ago
You could convert a singly-linked list to a doubly-linked list in O(n), and then apply your favorite doubly-linked solution. You could even do this in place without increasing the size of each node at the cost of doubling the size of variables that point to nodes and slightly lowing down stepping through the list. You do this by storing the next and previous pointers for each node in the same location, xor'ed together. That doubles the size of variables that point to nodes and slows down stepping because you have to turn them into structs that store both a pointer to the node and a pointer to an adjacent node and update both of these pointers as you move through the list.
- jandrese 9y ago
  If you're willing to burn O(n) memory on it you could just create an array of pointers to the nodes in the list and then use that to build the balanced tree. It's probably faster than iterating over the sublist every time to find the center. This assumes of course that the list is sorted. If not, you should probably sort the list first to avoid driving yourself insane. If memory is too tight to make temporary storage and the list is too big to sort and you want a perfectly balanced tree then you've got an interesting problem on your hands.
  - pklausler 9y ago
    You can sort a linked list in O(nlog(n)) time with O(log(n)) space, and then convert it to a balanced binary tree in O(nlog(n)) time and O(log(n)) space. EDIT: demonstration: sortList [] = [] sortList [x] = [x] sortList xs = merge (sortList as) (sortList bs) where (as, bs) = split xs split [] = ([], []) split [x] = ([x], []) split (x:y:rest) = let (xs, ys) = split rest in (x:xs, y:ys) merge xs [] = xs merge [] ys = ys merge (x:xs') ys@(y:_) | x <= y = x : merge xs' ys merge xs (y:ys) = y : merge xs ys data Tree a = Empty | Node a (Tree a) (Tree a) deriving(Show) balancedTree xs = mktree (length xs) xs where mktree 0 [] = Empty mktree n xs = Node x (mktree n' less) (mktree (n - 1 - n') more) where n' = (n - 1) `div` 2 (less, (x:more)) = splitAt n' xs listToBalancedTree :: Ord a => [a] -> Tree a listToBalancedTree = balancedTree . sortList
cbarrick 9y ago
Lol, I like how no one is talking about DSW in the replies to the comment about DSW. > [F]ind middle, use it as root, recursively build two subtrees. That's not DSW. DSW should be way more efficient. > With a singly-linked list, it's much harder; I don't know [...] if a more efficient [...] algorithm exists. This is DSW. DSW starts with a sorted linked list--called a "vine"--and builds the tree from that, in place. The vine is a singly linked list in the sense that you only need the successor pointer (though each node obviously needs space for a predecessor pointer since it's being turned into a tree). The algorithm is O(n) time and O(1) space and is actually very elegant. Essentially, you treat the list as a completely unbalanced tree skewed to the right. Then you repeatedly apply a `compress` routine that scans down the far right path in the tree to balance it. From Wikipedia routine vine-to-tree(root, size) leaves ← size + 1 − 2^⌊log2(size + 1))⌋ compress(root, leaves) size ← size − leaves while size > 1 compress(root, ⌊size / 2⌋) size ← ⌊size / 2⌋ routine compress(root, count) scanner ← root for i ← 1 to count child ← scanner.right scanner.right ← child.right scanner ← scanner.right child.right ← scanner.left scanner.left ← child Both the naive algorithm and DSW are O(n), but the naive algorithm has a time complexity of about 2n while DSW has a time complexity of about 0.63n, assuming we start with a vine.