[June 10 - June 16]

My fingers code faster than I can think!

Coding info

In the first half of this week, I completed the Red Black Trees class. In the second half, I worked on Binary Indexed Trees (which can also be interpreted as Fenwick Trees).

For Red Black Trees, the following methods have been implemented in the C++ backend, and tested exhaustively:

  • insert()
    • _get_parent()
    • _get_grand_parent()
    • _get_sibling()
    • _get_uncle()
    • _is_onleft()
    • _is_onright()
    • __fix_insert()
  • delete()
    • _find_predecessor()
    • _transplant_values()
    • _has_one_child()
    • _is_leaf()
    • _has_two_child()
    • __has_red_child()
    • _replace_node()
    • __walk1_walk_isblack()
    • __left_left_siblingcase()
    • __right_left_siblingcase()
    • __left_right_siblingcase()
    • __right_right_siblingcase()
    • __fix_deletion()
    • _remove_node()
    • _delete_root()
    • __leaf_case()
    • __one_child_case()
    • __two_child_case()
  • All tree traversals (OOPS concepts used to resuse code)

For Binary Indexed Trees, I’ve implemented the following methods in the C++ backend:

  • update()
  • get_prefix_sum()
  • get_sum()

Relevant PRs:

PR for RedBlackTrees (merged): #560

PR for BinaryIndexedTrees (merged): #561

In the following week, I will implement Splay Trees in the C++ backend.

Learnings/Difficulties

Everything is now going smoothly! My fingers code faster than I can think! I’ve understood the process and now become good at it, yay.


Thanks to my mentor, Gagandeep Singh, for his support throughout.

See you again after an amazing week! 😊