Talk:Binary search tree/GA2

GA Review

Article (edit | visual edit | history) · Article talk (edit | history) · Watch

Reviewer: Ewdqwdq (talk · contribs) 17:38, 8 April 2022 (UTC)

@Ewdqwdq: Thanks for taking this, if there are any improvements that you want to be made, please list them out. I will copy edit and make those changes ASAP. Regards, WikiLinuz {talk} 🍁 17:42, 8 April 2022 (UTC)

Who is Ewdqwda?

Hello Ewdqwdq. Who are you? Your username resembles a password, and your account is only 12 days old. Please confirm you're not a sockpuppet. Timhowardriley (talk) 21:15, 8 April 2022 (UTC)

That account is my alt. Is that okay?? Eluike (talk) 21:42, 8 April 2022 (UTC)

Simplify to a broader audience

I'm very interested in this article. I would like to understand it enough to incorporate binary search trees (BST) into my code library. However, even though I was exposed to BSTs in two courses (Graph Theory and Data Structures), this article is over my head. It's probably technically correct, but it needs to be heavily expanded. For example, I referred back to my Data Structures textbook to realize that BSTs are an extension of binary trees. Well, the first paragraph after the lead should be an explanation of binary trees and how this article extends them. However, it shouldn't read like binary tree because I can't understand that either. Instead, it should fully define in as simple of terms as possible all the jargon. This is not an easy task. This wikipedia article explains the goal: Wikipedia:Make technical articles understandable. I learned from a published author (http://www.jimchurchphoto.com/JimBio.html) to write at the 8th grade level. I'm also motivated by "Up Goer Five". It's an attempt to explain rocket science at the Elementary school level. See https://www.explainxkcd.com/wiki/index.php/1133:_Up_Goer_Five . Nonetheless, I wish the editors of this article good reviews. Timhowardriley (talk) 22:13, 8 April 2022 (UTC)

@Timhowardriley: I will copy-edit it. WikiLinuz {talk} 🍁 22:23, 8 April 2022 (UTC)

New review b/c first reviewer is blocked

I'm going to focus on the first Good Article criterion:

1. Well written: Yes, the prose is clear and concise. It complies with the manual of style guidelines for lead sections, layout, words to watch, fiction, and list incorporation. However, it falls short of being understandable to an appropriately broad audience. Instead, it seems understandable only to those who already know Binary Search Trees very well. I only sort-of know about BSTs, and it's over my head. The article should build a BST from scratch and not rely on the reader's prior knowledge.

Because every BST component is an abstract construct, they need to be converted into visuals. (On the other hand, concrete constructs, like the components of bridges, have innate visuals.) The textbook I'm using to justify this review uses a family tree as its BST visual. It uses nouns like "parent" and "child". It also uses tree components like "branch" and "leaf".

Binary Search Tree

Here are the BST components that should be made visual.

1. Rooted tree is the foundation.
2. Vertices store family members.
3. Edges are branches that represent parent/child relationships.
4. Root vertex starts the tree.
5. Parent vertices have edges pointing to each child vertex.
6. Child vertices have only one edge pointing in from its parent vertex.
7. A child vertex may be a parent to a subtree.
8. A child vertex that is not a parent is a leaf.
9. The level of a vertex is the number of edges up to the root.
10. The height of a tree is the maximum level.
11. A disk-drive directory structure is an example of a rooted tree.
12. Slash (/) or backslash (\) is the root directory.
13. A directory without any subdirectories or files is a leaf.
14. A directory with subdirectories or files is a parent.
15. Each file in a directory is a leaf.
16. A binary tree is a tree with at most two children.
17. The first child is called the left child.
18. If the left child is also a parent, then the left child is also called the left subtree.
19. The second child is called the right child.
20. If the right child is also a parent, then the right child is also called the right subtree.
21. A binary search tree is a binary tree that is strategically populated to quickly search through.
22. Each vertex in a BST has a key which is used to search.
23. Each vertex in a BST also has a memory pointer to the data record associated with the key.
24. New verticies are inserted into the tree such that 1) the keys of all left subtrees are smaller than this key and 2) the keys of all right subtrees are larger than this key.
25. The first vertex inserted into an empty tree becomes the root.
26. Each additional vertex inserted into the tree must have its key compared with the existing keys in the tree.
27. If an additional vertex’s key is less than the parent vertex, then the new vertex must be someplace on the left subtree.
28. If an additional vertex’s key is greater than the parent vertex, then the new vertex must be somplace on the right subtree.
29. If an additional vertex encounters a leaf, then the additional vertex becomes the left child of the leaf.
30. If an additional vertex encounters a parent with only a left child, and if its key is greater than the left child’s key, then the additional vertex will become the right child.
31. If an additional vertex encounters a parent with both children, and if its key is less than the parent’s key, then the additional vertex will join the left subtree.
32. If an additional vertex encounters a parent with both children, and if its key is greater than the parent’s key, then the additional vertex will join the right subtree.

Of course, this list needs to be formed into an essay. If each major step had a representative diagram, then that would be better.

C++ implementation

Instead of pseudo code, the article should have a functioning implementation. The reader then could copy/paste into a compiler to run. Who could claim that's not good? Here's a start:

// Filename: vertex.h

class VERTEX {
public:
    VERTEX(
        char *key,
        void *record );

    char *key;
    void *record;

    // I'm only guessing C++ supports recursive structures; C does not.
    VERTEX *left_child;
    VERTEX *right_child;

    VERTEX *insert(
        char *key,
        void *record );

    VERTEX *search(
        char *key );
}

// Filename: vertex.cpp

#include "vertex.h"

VERTEX::VERTEX(
        char *key,
        void *record )
{
    // Actual code
}

VERTEX *VERTEX::insert(
    char *key,
    void *record )
{
    // Actual code
}

VERTEX *VERTEX::search(
    char *key )
{
    // Actual code
}

// Filename: binary_search_tree.h

#include "vertex.h"

class BINARY_SEARCH_TREE {
public:
    BINARY_SEARCH_TREE( void );

    VERTEX *root;

    void insert(
        char *key,
        void *record );

    void *search(
        char *key );
}

// Filename: binary_search_tree.cpp

#include "binary_search_tree.h"

BINARY_SEARCH_TREE::BINARY_SEARCH_TREE( void )
{
    // Actual code
}

void BINARY_SEARCH_TREE::insert( char *key, void *record )
{
    // Actual code
}

void *BINARY_SEARCH_TREE::search( char *key )
{
    // Actual code
}

// Filename: person.h

class PERSON {
public:
    PERSON( char *full_name );
    char *full_name;
    char *street_address;
    char *city;
    char *state_code;
    char *zip_code;
}

// Filename: person.cpp

#include "person.h"

PERSON::PERSON( char *full_name )
{
    // Actual code
}

// Filename: binary_search_tree_driver.cpp

#include <iostream>
#include "binary_search_tree.h"
#include "person.h"

void main( void )
{
    BINARY_SEARCH_TREE *binary_search_tree =
        new BINARY_SEARCH_TREE();

    PERSON *first_person = new PERSON( "First Person" );
    binary_search_tree.insert(
        first_person->full_name,
        first_person );

    PERSON *second_person = new PERSON( "Second Person" );
    binary_search_tree.insert(
        second_person->full_name,
        second_person );

    PERSON *search_person =
        binary_search_tree.search(
            "First Person" );

    std::cout
        << "Search result = " << search_person->full_name << "\n";
}

# Filename: makefile

all: binary_search_tree_driver

clean:
    rm binary_search_tree_driver *.o

binary_search_tree_driver:            \
    binary_search_tree_driver.cpp     \
    binary_search_tree.o              \
    vertex.o
    c++ binary_search_tree_driver.cpp \
        binary_search_tree.o          \
        vertex.o                      \
        -o binary_search_tree_driver

binary_search_tree.o:                 \
    binary_search_tree.cpp            \
    binary_search_tree.h
    c++ -c binary_search_tree.cpp

vertex.o: vertex.cpp vertex.h
    c++ -c vertex.cpp

Final assessment

Once this foundation is established, then the article's remaining information will resonate. Final assessment: failed. Submitted, Timhowardriley (talk) 00:12, 11 April 2022 (UTC)

@Timhowardriley: No, it's the worst possible idea to suggest a C++ implementation. See MOS:PSEUDOCODE. Articles should not use a language-specific implementation, especially a C++ one. I'm sorry, but I don't think you're well-versed with our policies on computer science (algorithms and data structures) to give a review. We don't host code for readers to copy-paste, and compile; Wikipedia is WP:NOTREPOSITORY. Your final assessment should be dismissed. WikiLinuz {talk} 🍁 03:00, 11 April 2022 (UTC)

I agree that a C++ implementation would not be a good idea here. Even if there were a need for a language-specific implementation (which I am not seeing), one that's spread across eight files including a makefile would not be the right choice. XOR'easter (talk) 18:00, 11 April 2022 (UTC)

• Fair enough. My opinion was worded, "Instead of pseudo code, the article should have a functioning implementation." However, lacking a functioning implementation was not the cause for my rejection. Instead, the cause of my rejection was because it wasn't understandable to an appropriately broad audience. My suggestion for improvement was to build the subject matter from scratch. Don't rely on the reader to already know about trees, binary trees, and the need for computers to search for data blocks quickly. Timhowardriley (talk) 18:25, 11 April 2022 (UTC)
• Regarding the existing pseudo code: Missing is the corresponding data structure. A BST is an abstract datatype. The datatypes in the data structure are equally important to the pseudo code. Finally, the article should explain early on that storing and retrieving the key is not the underlying problem to be solved. The underlying problem to be solved is to quickly access the key's data block. After all, a BST is a container type. Displaying the data structure will show the reader that there's a pointer to the data block. Timhowardriley (talk) 18:44, 11 April 2022 (UTC)
• My suggestions are in good faith. I get no pleasure passing judgement. Timhowardriley (talk) 18:44, 11 April 2022 (UTC)

@Timhowardriley: If you don't know what you're doing, it's best to ask it first prior to ineptly failing a GA review and furthering disruption. WikiLinuz {talk} 🍁 03:28, 11 April 2022 (UTC)

I stand by my assessment. If C++ is not desirable, then a pseudo language will suffice. However, the syntax should support pointers as they are needed for container types. And please don't wikihound me because I assumed the responsibility of this review. This post was unwarranted: https://en.wikipedia.org/w/index.php?title=Talk:Computer_program&diff=prev&oldid=1082050227 . Timhowardriley (talk) 05:48, 11 April 2022 (UTC)

I suggest that you get acquainted with the relevant policies that govern code farm on articles prior to assuming responsibilities. WikiLinuz {talk} 🍁 06:05, 11 April 2022 (UTC)

@Timhowardriley: You clearly don't know what you're doing, espacially after your 2nd attempt. Please refrain from further disruptive editing. I shall wait for inputs from another editor. WikiLinuz {talk} 🍁 06:14, 11 April 2022 (UTC)

• Regarding "You clearly don't know what you're doing": Please avoid personal attacks. Additionally, I do know what I am doing. I'm advising the editors of this article to expand the audience set. The current version of the article assumes the reader knows:

1. what a tree it.
2. what a binary tree is.
3. that the purpose of the algorithm is to quickly search for data blocks.
4. that a BST is an abstract datatype and knows the contents of the data structure.
5. that a BST is a container type and there's a pointer to the key's data block.

These assumptions need to be addressed before I would label this article GA.

• Regarding "Please refrain from further disruptive editing.": My words are polite, and my opinions are in good faith. Timhowardriley (talk) 23:30, 11 April 2022 (UTC)

  Not a personal attack, those were your behavior in here, here, here, and above. All those points were already addressed in the current revision of the article, maybe you should re-read the article. As a guy who literally works with modern C++17 systems at production for a living, the code you've written above is poor and hardly has anything to do with the article - seems to be a code that a high-school student who just finished with basic C++ tutorials would write. What is a BST "driver" doing there? Clearly you're not trying to implement the driver pattern. And, what do classes like "PERSON" has anything to do with an encyclopedia article? I know C++, and that's why I'm avoiding it. Wikipedia articles are written in a language-agnostic way, not in my or your favorite language. Every standard API that a BST container would have is covered in the article at Binary_search_tree#Operations, it's up to the users to write an implementation over that specification. --WikiLinuz {talk} 🍁 00:33, 12 April 2022 (UTC)

  Again, Timhowardriley, you do not have to review this article. As I already said, you lack the understanding of our policies guiding WP:GAN/I and source code. Work on other areas of Wikipedia until you're acquainted with the cited policies. If you continue this disruptive behavior, as you did for the 3rd time here, you are escalating this to the admin boards. --WikiLinuz {talk} 🍁 00:42, 12 April 2022 (UTC)

I'm going to invoke Wikipedia:Civility. It says, "Stated simply, editors should always treat each other with consideration and respect. They should focus on improving the encyclopedia while maintaining a pleasant editing environment by behaving politely, calmly and reasonably, even during heated debates." Exit — stage right. Timhowardriley (talk) 01:10, 12 April 2022 (UTC)

Why don't you address the points I raised? I'm not going to repeat what I said over and over. --WikiLinuz {talk} 🍁 01:29, 12 April 2022 (UTC)

Because I don't want to play in your sandbox. Bye-bye. Timhowardriley (talk) 02:31, 12 April 2022 (UTC)