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:

Also, visit:

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. 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.

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