Talk:Binary search tree

Request for 3O

On 19 Aug 2021 user:Nomen4Omen had entered the following line into WP:Third opinion#Active disagreements:

  # Talk:Binary_search_tree#Changes of WikiLinuz as of 30 July 2021. Disagreement about placement and naming of functions and since yesterday about 'ugliness'. 07:33, 19 August 2021 (UTC)

–Nomen4Omen (talk) 13:47, 23 August 2021 (UTC)

Response to third opinion request:

Dear WikiLinuz and Nomen4Omen; good afternoon from the UK. I am Springnuts: AFIK I have not previously edited this article, nor have I interacted with either of the editors in this disagreement. I note that both of you have put considerable effort into, and are committed to, improving the encyclopedia - thank you! However, Wikipedia is not a textbook, so your work has, I am afraid, been misplaced. Sorry, but there it is. The reason is that this whole section falls short of the policy at WP:TECHNICAL. It's far too detailed for the average reader. The rule of thumb is here: WP:ONEDOWN. With all respect, your efforts, laudable as they are, belong somewhere else - perhaps a blog or forum. My 3O then, for what it is worth, is that one or other of you - or a third party - reduces the section here: Binary_search_tree#Operations to no more than four paragraphs, briefly covering: introduction; lookup, insertion and deletion of an element. Get rid of all the notes, then whilst you are about it simplify this section: Binary_search_tree#Examples_of_applications. Finally, ensure that this section: Binary_search_tree#Further_reading has some good pointers in it - five or six should be plenty - so that those who wish to study the topic in the detail and at the level you clearly both possess can do so. This is my 3O. I hope you will accept it, but you are free to disagree of course. With my best wishes to you both, Springnuts (talk) 16:56, 21 August 2021 (UTC)

Source Addition

There's this helpful site called visualgo.net that includes helpful demonstrations and interactive examples of computer science concepts, including the binary search tree. Could someone please add this as a source? ScientistBuilder (talk) 21:45, 13 October 2021 (UTC)ScientistBuilderScientistBuilder (talk) 21:45, 13 October 2021 (UTC)

Added the site as one of the external links in this revision diff. add this as a source, book by Steven Halim passes WP:RS/SPS and the media can be used on Wikipedia since the site effectively states CC-BY on its ToS. WikiLinuz (talk) 22:30, 13 October 2021 (UTC)

That site was aggressively spammed a few years ago and duplicates material we already have. I took it back out. - MrOllie (talk) 22:33, 13 October 2021 (UTC)

aggressively spammed? Could you link me to that? I don't know about that event. WikiLinuz (talk) 22:36, 13 October 2021 (UTC)

An IP added it to a couple dozen articles, I don't have anything specific to link to about it. - MrOllie (talk) 22:40, 13 October 2021 (UTC)

To mention, there is also a notable site hosted by Stanford University department which we use on BST visualization as an external link on few articles. Given this is written by an academic, I seriously doubt that it's aggressively spammed. WikiLinuz (talk) 22:42, 13 October 2021 (UTC)

People spam links for all sorts of reasons. Ego is as powerful a motive as profit. But at any rate we already have a link that provides the same sort of content. - MrOllie (talk) 22:44, 13 October 2021 (UTC)

There's a difference between spamming and linking to a resource hosted by an academic or a university's department on articles. In the later case, a link added of good faith, effectively passes WP:ELNO #11 for the reasons mentioned. It's only WP:LINKSTOAVOID if there it's some promotional website which is trying to attract traffic or outright irrelevant. Also, if we already have a link that provides the same sort of content, we give WP:DUE to the best one, which should be ranked objectively. WikiLinuz (talk) 22:54, 13 October 2021 (UTC)

I'm not saying you're spamming it, but when a link is previously spammed, and we already have another link that is much the same thing, it is a factor in which one we should keep. We really don't need duplicates. MrOllie (talk) 23:08, 13 October 2021 (UTC)

1 is clearly better than currently existing 2 if we visit and use it. Given that, I'm inclined towards replacing it with the better one if it seems like duplicates. WikiLinuz (talk) 23:13, 13 October 2021 (UTC)

@MrOllie: I've already objectively mentioned why that link should be added on my previous comments. If you WP:JUSTDONTLIKEIT, explain me here. Do not play revert wars. You don't seem to support your claims of the link being previous spammed through evidence. Prove me wrong if you wanted to keep the previous link, if you're not gonna do that, I'll revert this diff. WikiLinuz (talk) 09:24, 14 October 2021 (UTC)

Your argument, conversely, is just ILIKEIT. Other people frequent this talk page, at this point I think it is best to maintain the status quo ante bellum until one of them chimes in. Accusing me of playing revert wars while simultaneously pledging to revert war yourself is rather inconsistent, you might want to think about it. - MrOllie (talk) 11:27, 14 October 2021 (UTC)

GA Review

This review is transcluded from Talk:Binary search tree/GA3. The edit link for this section can be used to add comments to the review.

Reviewer: Mhawk10 (talk · contribs) 05:16, 14 May 2022 (UTC)

Hello! I'll take a look at this article and give feedback over the next couple of days. — Ⓜ️hawk10 (talk) 05:16, 14 May 2022 (UTC)

@Mhawk10: Thanks for taking this one. If there are any copy edits, improvements or changes you want to be made, please let me know. I'll make the revisions ASAP. --WikiLinuz {talk} 🍁 12:44, 14 May 2022 (UTC)

@WikiLinuz: I've placed the article on-hold, per below. I'm still working through and spot-checking refs, though there are going to need to be some improvements made if this is going to become a GA. — Ⓜ️hawk10 (talk) 18:30, 16 May 2022 (UTC)

@Mhawk10: Thanks. Keep them posted, I'll incrementally make those requested changes within the standard seven days on-hold period. --WikiLinuz {talk} 🍁 18:33, 16 May 2022 (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.	No spelling or grammar errors that I can detect on another read through, aside from the issue I'm raising in the area on original research. Once that's fine, this should be good to go from a prose quality perspective. — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC) Resolved. — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC)
	1b. it complies with the Manual of Style guidelines for lead sections, layout, words to watch, fiction, and list incorporation.	There are issues with compliance with MOS:LEAD. The lead does not include any materials from the "Examples of Applications", "Types", and "History" sections, while it probably should. The length of the lead was something that was noted in Talk:Binary search tree/GA1 but has not been fixed. This technically would be enough for a quick fail, though it's often best to re-write the lead after all of the other fixes are made so I think it's best to WP:IAR and put this on hold rather than give a quick fail. — Ⓜ️hawk10 (talk) 02:53, 16 May 2022 (UTC) Again, still no mention of the history in the lead. Why? — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC) Resolved. — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC)
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.	There indeed is a references section that is MOS-compliant. — Ⓜ️hawk10 (talk) 18:32, 16 May 2022 (UTC)
	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).	All of the citations that are in the document are reliable sources. — Ⓜ️hawk10 (talk) 00:01, 24 May 2022 (UTC)
	2c. it contains no original research.	The second edition of the MIT textbook that is cited for the Tree-Predecessor pseudocode is left as an exercise to the reader (Exercise 12.2-3) in the cited textbook. While the text notes that "The procedure TREE-PREDECESSOR, which is symmetric to TREE-SUCCESSOR", the citation is a bit weak to support the specific pseudocode in the article. — Ⓜ️hawk10 (talk) 01:51, 16 May 2022 (UTC) Also, can you show that the "tree-deletion" pseudocode operates the same as the "TREE-DELETE" pseudocode in the cited source? If so, it's fine as a routine calculation, but this is something that you are going to need to demonstrate here. — Ⓜ️hawk10 (talk) 01:51, 16 May 2022 (UTC) Binary search trees support three main operations: lookup (checking whether a key is present), insertion, and deletion of an element. The latter two possibly change the structural arrangement of the nodes in the tree, whereas the first one is a navigating and read-only operation. Other read-only operations are traversal, verification, etc. needs a citation. The end of that sentence also probably could be improved flow-wise. — Ⓜ️hawk10 (talk) 00:01, 24 May 2022 (UTC) Again, this still should have a citation and should still be rephrased. — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC) This has been made moot by the removal of the material. — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC)
	2d. it contains no copyright violations or plagiarism.	I've acquired a copy of Introduction to Algorithms, Second Edition. The cited pages of the book appear to give pseudocode that contains the same function names as are in the book, though the pseudocode itself is transformed so as to not be a verbatim copy of what's in the book. The book was published in the United States, so the copyrights are exclusively governed by U.S. law. Copyrights in the United States are not valid when there are a very limited set of ways in which an idea can be expressed, so the pseudocode for those algorithms per se is not eligible under copyright protection. However, the choice to use "Tree-Search" for the name of the recursive search function and "Iterative-Tree-Search" for the iterative search function alongside the use of "Tree-Successor", "Tree-Maximum", "Tree-Minimum", "Tree-Insert", "Tree-Delete", and " probably extends beyond this limited exception to copyright—it's certainly possible to give the functions different names than are given in the MIT textbook. — Ⓜ️hawk10 (talk) 01:51, 16 May 2022 (UTC) This issue has been remediated. — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC) If you'd like to take action against a source that copied Wikipedia without attribution, this medium post showed 67% similarity to this article on WP:EARWIG. This is a case of a publication copying Wikipedia, so it does not pose an issue for the article's promotion to GA. — Ⓜ️hawk10 (talk) 02:05, 16 May 2022 (UTC)
3. Broad in its coverage:
	3a. it addresses the main aspects of the topic.	There is a lot written about self-balancing binary search trees in the academic literature, which appears to be a child topic of this article. The current article addresses this topic within the "types" section, but it doesn't really go in-depth into it. It also isn't quite structured like the typical parent-child article relation (for example, with the {{main article}} template as a header of a section or sub-section). — Ⓜ️hawk10 (talk) 02:14, 16 May 2022 (UTC) Similarly, the history section is really short. It might be worthwhile to briefly describe the history of the major variants of the binary search tree as well; Red-Black Trees, AVL Trees, etc. are worth prominently mentioning in this article and might be helpful in expanding the history section beyond a sentence. — Ⓜ️hawk10 (talk) 02:44, 16 May 2022 (UTC) I like the way that you handled making this more like a summary style article and I think it more appropriately balances these sorts of things. — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC)
	3b. it stays focused on the topic without going into unnecessary detail (see summary style).	The article seems to have no problems here. — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC)
	4. Neutral: it represents viewpoints fairly and without editorial bias, giving due weight to each.	Looks fine as of now. — Ⓜ️hawk10 (talk) 02:34, 16 May 2022 (UTC)
	5. Stable: it does not change significantly from day to day because of an ongoing edit war or content dispute.	I don't see any edit warring recently. — Ⓜ️hawk10 (talk) 02:35, 16 May 2022 (UTC)
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.	The images used in the article are tagged with their copyright status. — Ⓜ️hawk10 (talk) 18:30, 16 May 2022 (UTC)
	6b. media are relevant to the topic, and have suitable captions.	Images pertain to the material and have policy-compliant captions. — Ⓜ️hawk10 (talk) 18:30, 16 May 2022 (UTC)
	7. Overall assessment.	On hold for now. — Ⓜ️hawk10 (talk) 18:30, 16 May 2022 (UTC) Passed! — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC)

@Mhawk10:

• 1b - I've copy-edited the lead to include information from other sections.
• 2c - I've added additional references for the predecessor pseudocode. The "BST-Delete" is nearly identical to that of the sourced material, and the only variant is the internal call to "TRANSPLANT", which is "Shift-Nodes" in the article.
• 2d - I've modified the subroutine names.
• 3a - I've rewritten the history section to include self-balancing aspects, and also copy-edited the "types" section.

--WikiLinuz {talk} 🍁 04:13, 20 May 2022 (UTC)

@WikiLinuz: thank you for the ping! I'll take another look through and give more feedback when I get a chance. — Ⓜ️hawk10 (talk) 04:24, 20 May 2022 (UTC)

A drive-by comment (re GACR 3a or maybe 4): The coverage of optimal binary search trees is currently totally inadequate. It is ungrammatical (the first noun phrase of the first sentence is missing its article). It fails to properly describe the problem (optimal in this context means in terms of average time with respect to some distribution or sequence of updates, not worst case time). It is misclassified under "self-balancing" (much of the work in this area is on static algorithms for constructing these trees, not on self-balancing trees). It fails to mention the time bounds for these static problems, or even the basic fact that these trees can be constructed in polynomial time. It fails to mention the connection to online algorithms and competitive ratios via the dynamic optimality conjecture for splay trees and greedy-ass trees and tango trees. If this is representative of the whole article I can see why this is on its third review after two previous contentious reviews — this is a level of unreadiness for GA that cosmetic edits alone won't fix. —David Eppstein (talk) 18:38, 22 May 2022 (UTC)

I've taken a note of your comment on the optimal BST. But I don't think I can access Wikipedia for a day or two since I'm facing power outage for 2 days due to a major storm in Toronto area. I'm not sure when the power will be back.

https://www.bbc.com/news/world-us-canada-61541653.amp WikiLinuz-mobile (talk) 21:35, 22 May 2022 (UTC)

@WikiLinuz-mobile: Stay safe! I can keep this on hold for as long as need be to make the changes. — Ⓜ️hawk10 (talk) 21:43, 22 May 2022 (UTC)

@Mhawk10: Thank you. Power is back in my neighborhood, I'll be working on the mentioned remarks starting today. --WikiLinuz {talk} 🍁 09:21, 25 May 2022 (UTC)

@Mhawk10: I've made substantial revisions to the particular section in question, shortened the body, and removed UNDUE text. As a result, I've decided to confine the article to BST. Please take a look at the current revision and let me know if you like some changes. --WikiLinuz {talk} 🍁 05:10, 6 June 2022 (UTC)

I will take a look through over the next couple of days. — Ⓜ️hawk10 (talk) 05:38, 7 June 2022 (UTC)

@Mhawk10: I received a notice from Legobot on the 8th saying that the nomination would automatically fail in 7 days. It's been five days (June 13th), so it'd be great if you could look through and note any changes before auto-fail. Thanks. --WikiLinuz {talk} 🍁 23:25, 13 June 2022 (UTC)

Hi! I'll get to that tonight. I promise it won't auto-fail you; the only way that it would fail is if I (or another reviewer) were to fail it. — Ⓜ️hawk10 (talk) 23:26, 13 June 2022 (UTC)

@WikiLinuz: I've updated the table above. I'm still not seeing any mention of the history section in the lead, which for me constitutes an MOS:LEAD violation. Please remediate this and the other issues that remain. — Ⓜ️hawk10 (talk) 04:51, 14 June 2022 (UTC)

@Mhawk10:

• 2c: That paragraph merely states the operations within the sub-section. But I think the operations themselves are self-explanatory and don't need a secondary introduction, so I've taken them away.
• 1b: I've copy-edited to include things from the history section in the lead (regarding attribution and invention of the self-balancing variants to address a critical issue that BST suffers from). Please let me know if you'd like something else to be summarized in the lead.

--WikiLinuz {talk} 🍁 05:44, 14 June 2022 (UTC)

Passed! Congrats on the GA. — Ⓜ️hawk10 (talk) 05:48, 14 June 2022 (UTC)

A Commons file used on this page or its Wikidata item has been nominated for deletion

The following Wikimedia Commons file used on this page or its Wikidata item has been nominated for deletion:

• Binary search tree deletion illustration.png

Participate in the deletion discussion at the nomination page. —Community Tech bot (talk) 16:52, 22 December 2022 (UTC)