marcellonicoletti / bst-countwords Goto Github PK
View Code? Open in Web Editor NEWOperating Systems class: C language warm up. A binary search tree to count the words in a file
Operating Systems class: C language warm up. A binary search tree to count the words in a file
This may cause unintended problems if called with NULL or a NULL pointer.
Sub-issue of #16
Rotations maintain the rules of the binary search tree while changing the structure. They are essential to a basic self balancing tree.
Add functions allowing to return an array of NodeData of all the keys in the tree with an in order traversal. Could be used to populate a heap to get words in order of most to least (or vise-versa) common.
Sub-issue of #16
Rebalance is triggered when the difference between a node's left and right branchs' height exceeds 2. We need to know the height to do that.
Sub-issue of #10
Getting the min or max of a child is one step of replacing a node to be removed.
Also just handy to have.
I cannot maintain an accurate size tally. Change insert from void to bool/int to indicate whether a key was new or a repeat. (true = new -> increment size tally)
Create a file populated with many words with some of them duplicated. Will use this to test reading from a file.
The three primary operations for a BST are Insert, Search, Remove. I only have one of those currently. This will have some "sub-issues" surrounding auxiliary operations such as max & min.
The three primary operations for a BST are Insert, Search, Remove. I only have one of those currently. Should return a NodeData type pointer and allow caller to deal with raw NodeData.
This function will help illustrate the tree structure. Will have some way of indicating relationship between nodes containing the words not just the words in order.
Binary Search Trees optimize lookup by reducing the number of comparisons that need to be made by eliminating possibilities. In ideal cases BSTs can search in O(log_2(n))
but this requires the tree to be well balanced. If a tree isn't well balanced well ordered inputs can cause a bad case where search approaches or is O(n)
. To counter this the tree should keep itself pretty well balanced. This will produce little overhead on insert but create savings on future insert, search, or remove operations.
This issue will have "sub-issues" surrounding functions that will help implementation.
Assignment is to read words from a file and count them with a tree. This is part 1 of that.
This way BST.c will not need to be updated at all when changing data types. All changeable functions and structs should be moved to NodeData.c
Separate BST related code from main.c. First step towards reusability of tree code
Current comments are a bit out of date or simply are missing on newer functions.
Add a layer of abstraction to tree's data type. Tree itself won't directly know what kind of data it's holding. Should achieve through additional structures and typedefs that can be changed in a central place and cascade across all tree functions.
Test the tree directly, no need to read / write files. Create a few cases to see different tree structures.
Professor will provide a few files inputXX.txt with the list of words. Need to be able to easily change between these files.
Professor will provide inputXX.txt files and I can choose what goes in XX. Professor also gives expected output for each scenario in outputXX.txt
Need to create/update "myoutputXX.txt" file with the output of my program and I need to ensure that XX matches between the output and input files.
Assignment is to read words from a file and count them with a BST. This is part 2. Tree nodes will need to store a word and it's number of appearances.
A declarative, efficient, and flexible JavaScript library for building user interfaces.
๐ Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. ๐๐๐
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google โค๏ธ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.