Skip to main content
Code Review

Return to Answer

replaced http://codereview.stackexchange.com/ with https://codereview.stackexchange.com/
Source Link

I'd suggest:

  • If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
  • The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
  • Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.

I'd suggest:

  • If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
  • The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
  • Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.

I'd suggest:

  • If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
  • The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
  • Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.
Source Link
Petr
  • 3.1k
  • 18
  • 33

I'd suggest:

  • If you have the height of a node in the Node constructor, you don't need to create a separate function getBinTreeHt. It is error prone (what if you change the way the tree is constructed, or add another one?) and costly - each call to it is O(n). Instead, use smart constructors as shown in this answer. Then you'll get the heights computed automatically, with minimal overhead, and it will work correctly regardless of what kind of tree or how you'll be constructing it.
  • The implementation is now correct, but it is somewhat inefficient. Since you call splitInHalf for every Node you're constructing, the total time complexity will be O(n^2), as each this call computes length xs and splitAt mid xs, which are both O(n). There is no simple way how to fix that though, you'd need to re-thing the algorithm. (Hints: compute the length only at the beginning and then use it to compute the sizes of subtrees; try to consume the list from the beginning, without splitting, and pass around the unconsumed part, as you're building the tree; if you want, I can provide a code sample.)
  • Usually the main reason why you want to have a balanced tree is that you can search in it fast. In order to do that, you need the tree to have the property that all elements in the left (right) subtree of a node are less (greater) than the node's element. I don't know if this is your aim, but if it is, you probably want to modify the algorithm so that if it's given a sorted list, it'll create a balanced, properly ordered tree.
lang-hs

AltStyle によって変換されたページ (->オリジナル) /