Binary Search Tree and Red-Black Tree Python

I’m working on a Python exercise and need support.

This is for BST and RB Balanced Tree implementation

I have attached the .txt file and the code to import the numbers from the .txt file.

'''_x000D_
This function imports a text file and converts all numbers into integers and stores them in a list_x000D_
Input: A list to store the numbers and file name_x000D_
Output: Returns a list of imported numbers_x000D_
'''_x000D_
def importFile(randL, fname):_x000D_
    with open(fname, mode="r") as inFile:_x000D_
        for line in inFile:_x000D_
            l1 = line.strip('n').split(" ") # strip n at every line and split spaces to put in a list_x000D_
            for i, val in enumerate(l1):_x000D_
                if val == 'n':_x000D_
                    l1.remove(val)_x000D_
            randL.extend(l1)_x000D_
    # filters out " in list_x000D_
    randL = list(filter(None, randL))_x000D_
    # converts str to int for every element in list_x000D_
    for i, val in enumerate(randL):_x000D_
        j = int(val)_x000D_
        randL[i] = j_x000D_
    return randL

Read the following postings:

• 1. https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree (Links to an external site.)
  2. https://www.reddit.com/r/Python/comments/9allgh/wheres_pythons_damn_binary_search_tree/ (Links to an external site.)
  3. https://www.laurentluce.com/posts/binary-search-tree-library-in-python/ (Links to an external site.)

Also, visit:

• • https://pypi.org/project/binarytree/ (Links to an external site.)

I found the third posting (laurentluce (Links to an external site.)) above is very useful introduction to the beginners of BST implementation . You may read the blog in its entirety.

1. 1. Download or copy laurentluce (Links to an external site.)‘s library (from github)
   2. Add the following methods in the library:
      • getHeight () – returns the number of tree height from self
      • countNodes() – returns the number of total nodes in a given tree
   3. Create and populate a BST tree with the integer data from ‘rand1000000.txt’ file and count the tree height and the number of nodes using your own methods above.
      • Make sure add() and delete() work
   4. in descending order, traverse the tree to visit the contents of the tree of 1,000 nodes from “rand1000.txt” file ( or100 nodes if you prefer but make your own data file)
      • While traversing, print the node in English number format. For example if the number is 418,621, write it down “four hundred eighteen thousand six hundred twenty one”
      • Use Python “Generator” pattern using ‘yield‘
      • Feel free to use any Python standard data type available to map a number to English format
   5. Using pypi binarytree package or any other RB tree library you can find from the Internet, do steps 2 – 3 (don’t need 4 again) with a Red-Black tree.
      • https://pypi.org/project/bintrees/ ( a stopped project) (Links to an external site.)

deliverable:

1. (3 points) Did you read all the articles referenced above? This points counted only if you complete the extra credit assignment in its entirety.
2. ( 5 points) Heights of both trees (BST and RB BST) with 1 Million nodes
3. (7 points) The output of tree traversal displaying the numbers in English format