Anyway, Binary search trees are super useful. They're basically binary trees where the left node is less than the root node and the right node is greater than the root node. This makes finding stuff really easy because you really only need to compare the node, then ignore half of the tree. This means that the runtime of binary search trees (for the worst case) when you need to find something is very short (log n runtime).
The wrapper node of the binary search trees (BST) should initialize the root, the left and the right subtrees...Because well, they're supposed to have two kids: one left kid and one right kid.
The lab this week was actually pretty challenging. Most of our lab group only managed to finished the first part of count_less. (Even then people still felt time constraints)
What we had to do with count_less was count the number of items in the BST whose values were less than the given item. I think the most challenging part was determining what kind of if statements and else statements we had to go through.
There are two base cases. when the root does exist and when the root does not exist. If the root does exist, then you wouldn't count it (well, for obvious reasons), and if the root does exist, there are two things you do:
1) if the root is greater than or equal to the item, recurse to the left subtree (rerun the function itself on the left subtree)
2) if the root is less than the item, recurse both the left and right subtrees (count to see if there are items in either of the subtrees because it's possible for either to happen), and add a count for the root itself.
Looking back, the eight lines of code probably shouldn't have taken that long, but I think it took us a long time to really understand the BSTs as well as thinking of how to properly return the value.
What we had to do with count_less was count the number of items in the BST whose values were less than the given item. I think the most challenging part was determining what kind of if statements and else statements we had to go through.
There are two base cases. when the root does exist and when the root does not exist. If the root does exist, then you wouldn't count it (well, for obvious reasons), and if the root does exist, there are two things you do:
1) if the root is greater than or equal to the item, recurse to the left subtree (rerun the function itself on the left subtree)
2) if the root is less than the item, recurse both the left and right subtrees (count to see if there are items in either of the subtrees because it's possible for either to happen), and add a count for the root itself.
Looking back, the eight lines of code probably shouldn't have taken that long, but I think it took us a long time to really understand the BSTs as well as thinking of how to properly return the value.
No comments:
Post a Comment