GA toolbox |
---|
Reviewing |
Article (
|
visual edit |
history) ·
Article talk (
|
history) ·
Watch
Reviewer: Ganesha811 ( talk · contribs) 17:27, 4 August 2023 (UTC)
Hi! I'll be reviewing this article, using the template below. Sorry for the long wait! If you have any questions, feel free to ask them here. —
Ganesha811 (
talk)
17:27, 4 August 2023 (UTC)
Rate | Attribute | Review Comment |
---|---|---|
1. Well-written: | ||
![]() |
1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct. |
|
![]() |
1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation. |
|
2. Verifiable with no original research: | ||
![]() |
2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline. | |
![]() |
2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose). |
|
![]() |
2c. it contains no original research. | |
![]() |
2d. it contains no copyright violations or plagiarism. | |
3. Broad in its coverage: | ||
![]() |
3a. it addresses the main aspects of the topic. |
|
![]() |
3b. it stays focused on the topic without going into unnecessary detail (see summary style). | |
![]() |
4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each. |
|
![]() |
5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute. |
|
6. Illustrated, if possible, by media such as images, video, or audio: | ||
![]() |
6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content. |
|
![]() |
6b. media are relevant to the topic, and have suitable captions. |
|
![]() |
7. Overall assessment. |
When I picked this up I wasn't intending to count it towards the backlog but given the length of what I've managed to write, I'll query if it can be counted. The reviewer has tagged this as a second opinion, rather than abandoning the review, but in covering the criteria they had questioned/blank in the table at the top, I've managed to assess all the criteria.
The key issue is whether the topic balances readability, focus and explanation of technical terms in the manner appropriate for mathematical articles. I agree with David Eppstein that the minimum required knowledge (at least for the early part of the article) is introductory computer science: such topics as trees, traversals, recursion and heaps are assumed knowledge. (Even so, readers may need a moment to process, be unfamiliar with a term or two, or need a refresher—I'll confess to forgetting what a heap is.)
Some of these suggestions may contradict the previous reviewer:
When all numbers are distinct, the Cartesian tree is uniquely defined ...and then "distinct" is specified in both definitions in the body. Indeed, "the smallest" doesn't make sense if the sequence isn't distinct. Perhaps the first sentence could say "... a sequence of distinct numbers". When it gets to the last "Definition" paragraph, which seems to be the only place the non-distinct case is considered, this restriction can be explicitly relaxed. (FWIW: it seems in the non-distinct case there can be one Cartesian tree or many—I wonder if there's some interesting classification or counting problem here.)
To construct the tree, set the root equal to the smallest number in the sequence and recursively construct the left and right subtrees from the subsequences before and after this number.
Introduced by Vuillemin (1980) ...sentence is long enough to be split into two: the first on the introduction; the second on other applications.
may be constructed: "can be constructed" sounds more natural to me (same in the body).
These are mathematical structures rather than computer data structures, although Cartesian trees have been used as part of the definition of certain data structures ... As well, each node may have some associated data (a number, in the case of a Cartesian tree).can be cut as expected background knowledge; a reader who doesn't understand should follow the links (and confusion in binary tree or tree (data structure) about a tree being a mathematical structure are out of scope for this GA review).
Each node is associated with a single sequence value.– I don't think this is new information, so can be dropped. (And in fact, I feel this weak notion of "associated" drops the rigour of "uniquely defined by...")
That is, the left subtree ... and a similar ordering constraint holds ...– Looking to drop this last clause if at all possible, would it be sufficient to say "for each node, numbers in its left subtree occur before it in the sequence [and the same for the right]"?
One method is to simply process.
... right spine of the left tree .... If the parenthetical is supposed to be this definition you might need multiple sentences for the algorithm's description.
... up to a constant fraction of the elements in the current tree may be ...– I think "up to" is redundant to "may be".
in the first illustrationrequires quite a bit of scrolling and is going to be particularly confusing to anyone on mobile, who sees the image in this section immediately above this text. But I'm not sure the image is actually needed to make the point. Could the example be the (sub)sequence (12, 10, 20, 15, 18), where you just assert that 10 is the lowest common ancestor of 12 and 18 in the Cartesian tree? (I've chosen something where the ancestor isn't just the parent of the two numbers.)
Because lowest common ancestors ... the same bounds can be achieved for the range minimization problem using a data structure that ...
differ by ±1– just "differ by 1" is fine ("difference" generally means the absolute value).
Because a Cartesian tree is a binary tree, it is natural to use it ...– This bit feels more like an essay than a Wikipedia article. More matter-of-fact-ly, how about:
The Cartesian tree of a sorted sequence is a path where each node other than the leaf has a right child. As such, a binary search tree algorithm degenerates to sequential search. However, the Cartesian tree can be adapted into a more-balanced search tree by ...
(they have logarithmic depth with high probability)means exactly.
Random binary search trees had been studied for much longer– Strange tense. Maybe
Random binary search trees were an object of study before Cartesian trees.
the same good behavior carries over to treaps– I think this is already clear in context.
— Bilorv ( talk) 22:34, 8 August 2023 (UTC)
GA toolbox |
---|
Reviewing |
Article (
|
visual edit |
history) ·
Article talk (
|
history) ·
Watch
Reviewer: Ganesha811 ( talk · contribs) 17:27, 4 August 2023 (UTC)
Hi! I'll be reviewing this article, using the template below. Sorry for the long wait! If you have any questions, feel free to ask them here. —
Ganesha811 (
talk)
17:27, 4 August 2023 (UTC)
Rate | Attribute | Review Comment |
---|---|---|
1. Well-written: | ||
![]() |
1a. the prose is clear, concise, and understandable to an appropriately broad audience; spelling and grammar are correct. |
|
![]() |
1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation. |
|
2. Verifiable with no original research: | ||
![]() |
2a. it contains a list of all references (sources of information), presented in accordance with the layout style guideline. | |
![]() |
2b. reliable sources are cited inline. All content that could reasonably be challenged, except for plot summaries and that which summarizes cited content elsewhere in the article, must be cited no later than the end of the paragraph (or line if the content is not in prose). |
|
![]() |
2c. it contains no original research. | |
![]() |
2d. it contains no copyright violations or plagiarism. | |
3. Broad in its coverage: | ||
![]() |
3a. it addresses the main aspects of the topic. |
|
![]() |
3b. it stays focused on the topic without going into unnecessary detail (see summary style). | |
![]() |
4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each. |
|
![]() |
5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute. |
|
6. Illustrated, if possible, by media such as images, video, or audio: | ||
![]() |
6a. media are tagged with their copyright statuses, and valid non-free use rationales are provided for non-free content. |
|
![]() |
6b. media are relevant to the topic, and have suitable captions. |
|
![]() |
7. Overall assessment. |
When I picked this up I wasn't intending to count it towards the backlog but given the length of what I've managed to write, I'll query if it can be counted. The reviewer has tagged this as a second opinion, rather than abandoning the review, but in covering the criteria they had questioned/blank in the table at the top, I've managed to assess all the criteria.
The key issue is whether the topic balances readability, focus and explanation of technical terms in the manner appropriate for mathematical articles. I agree with David Eppstein that the minimum required knowledge (at least for the early part of the article) is introductory computer science: such topics as trees, traversals, recursion and heaps are assumed knowledge. (Even so, readers may need a moment to process, be unfamiliar with a term or two, or need a refresher—I'll confess to forgetting what a heap is.)
Some of these suggestions may contradict the previous reviewer:
When all numbers are distinct, the Cartesian tree is uniquely defined ...and then "distinct" is specified in both definitions in the body. Indeed, "the smallest" doesn't make sense if the sequence isn't distinct. Perhaps the first sentence could say "... a sequence of distinct numbers". When it gets to the last "Definition" paragraph, which seems to be the only place the non-distinct case is considered, this restriction can be explicitly relaxed. (FWIW: it seems in the non-distinct case there can be one Cartesian tree or many—I wonder if there's some interesting classification or counting problem here.)
To construct the tree, set the root equal to the smallest number in the sequence and recursively construct the left and right subtrees from the subsequences before and after this number.
Introduced by Vuillemin (1980) ...sentence is long enough to be split into two: the first on the introduction; the second on other applications.
may be constructed: "can be constructed" sounds more natural to me (same in the body).
These are mathematical structures rather than computer data structures, although Cartesian trees have been used as part of the definition of certain data structures ... As well, each node may have some associated data (a number, in the case of a Cartesian tree).can be cut as expected background knowledge; a reader who doesn't understand should follow the links (and confusion in binary tree or tree (data structure) about a tree being a mathematical structure are out of scope for this GA review).
Each node is associated with a single sequence value.– I don't think this is new information, so can be dropped. (And in fact, I feel this weak notion of "associated" drops the rigour of "uniquely defined by...")
That is, the left subtree ... and a similar ordering constraint holds ...– Looking to drop this last clause if at all possible, would it be sufficient to say "for each node, numbers in its left subtree occur before it in the sequence [and the same for the right]"?
One method is to simply process.
... right spine of the left tree .... If the parenthetical is supposed to be this definition you might need multiple sentences for the algorithm's description.
... up to a constant fraction of the elements in the current tree may be ...– I think "up to" is redundant to "may be".
in the first illustrationrequires quite a bit of scrolling and is going to be particularly confusing to anyone on mobile, who sees the image in this section immediately above this text. But I'm not sure the image is actually needed to make the point. Could the example be the (sub)sequence (12, 10, 20, 15, 18), where you just assert that 10 is the lowest common ancestor of 12 and 18 in the Cartesian tree? (I've chosen something where the ancestor isn't just the parent of the two numbers.)
Because lowest common ancestors ... the same bounds can be achieved for the range minimization problem using a data structure that ...
differ by ±1– just "differ by 1" is fine ("difference" generally means the absolute value).
Because a Cartesian tree is a binary tree, it is natural to use it ...– This bit feels more like an essay than a Wikipedia article. More matter-of-fact-ly, how about:
The Cartesian tree of a sorted sequence is a path where each node other than the leaf has a right child. As such, a binary search tree algorithm degenerates to sequential search. However, the Cartesian tree can be adapted into a more-balanced search tree by ...
(they have logarithmic depth with high probability)means exactly.
Random binary search trees had been studied for much longer– Strange tense. Maybe
Random binary search trees were an object of study before Cartesian trees.
the same good behavior carries over to treaps– I think this is already clear in context.
— Bilorv ( talk) 22:34, 8 August 2023 (UTC)