[SOLVED] Binary Search Tree and Red-Black Tree Python
Im 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.
''' This function imports a text file and converts all numbers into integers and stores them in a list Input: A list to store the numbers and file name Output: Returns a list of imported numbers ''' def importFile(randL, fname): with open(fname, mode="r") as inFile: for line in inFile: l1 = line.strip('n').split(" ") # strip n at every line and split spaces to put in a list for i, val in enumerate(l1): if val == 'n': l1.remove(val) randL.extend(l1) # filters out " in list randL = list(filter(None, randL)) # converts str to int for every element in list for i, val in enumerate(randL): j = int(val) randL[i] = j return randL
Read the following postings:
- https://stackoverflow.com/questions/2298165/pythons-standard-library-is-there-a-module-for-balanced-binary-tree (Links to an external site.)
- https://www.reddit.com/r/Python/comments/9allgh/wheres_pythons_damn_binary_search_tree/ (Links to an external site.)
- https://www.laurentluce.com/posts/binary-search-tree-library-in-python/ (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.
- Download or copy laurentluce (Links to an external site.)‘s library (from github)
- 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
- 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
- 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
- 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.
- (3 points) Did you read all the articles referenced above? This points counted only if you complete the extra credit assignment in its entirety.
- ( 5 points) Heights of both trees (BST and RB BST) with 1 Million nodes
- (7 points) The output of tree traversal displaying the numbers in English format