marcellonicoletti / bst-countwords Goto Github PK

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.