Add red-black tree

[czgdp1807]

Description of the problem

Example of the problem

References/Other comments

.. [1] https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
.. [2] https://github.com/codezonediitj/pydatastructs/wiki/Plan-of-Action-for-the-Projects

[VibavariG]

I would like to work on this issue. I am a beginner and i have done red black trees in java. I would like to try this. Please assign me this issue. I am a participant of GSSoC '20

[czgdp1807]

Hi @VibavariG This issue is reserved for RGSoC, 2020.
Please see this list of GSSoC, 2020 issues.

[nehasangeetajha]

I would like to work on this issue. I am participant for RGSOC'20 as well

[czgdp1807]

@nehasangeetajha Sure, you can start your work by coming up with an API design for red-black trees. Describe your design in the comments below.

[soumyarao17]

Hey! I would love to contribute to the same. Can I just know if the code has to be in Python only? Or can I use C++ as well?

[czgdp1807]

Hi @wowrao17 If @nehasangeetajha doesn't come up with an API design for red-black for some days(may be 3 or 4) then feel free to start your work on this issue.
The code should be in Python only, however before jumping to implementation we will focus on design aspect. Let us know your queries/doubts.

[soumyarao17]

Okay, Thank you :)

[nehasangeetajha]

I have come up with following API design for red black tree.
node class with following data members:

1. data - data stored in current node
2. parent - reference to parent of current node
3. left - reference to left child of current node
4. right - refernce to right child of current node
5. color - color(either red or black) of current node

Red Black tree class with following methods:

1. insert : Function to insert a new node in current tree
2. delete : Function to delete a node from the tree
3. print : Function to print the nodes of current red black tree
4. get_root: To get root of the tree
5. left_rotate
6. right_rotate
7. maximum
8. minimum
9. predecessor
10. successor
11. postorder
12. preorder
13. inorder
    with some private helper functions as and when required.
    Thank you.
    Please suggest improvements if any so that i can start working on it

[czgdp1807]

node class with following data members:

1. data - data stored in current node
2. parent - reference to parent of current node
3. left - reference to left child of current node
4. right - refernce to right child of current node
5. color - color(either red or black) of current node

Can we extend the already existing TreeNode class and add color attribute to the subclass.

3. print : Function to print the nodes of current red black tree

Use, __str__ to stringify the red black trees.

• left_rotate
• right_rotate

Are these similar to the rotations in AVLTree?

• maximum
• minimum
• predecessor
• successor

What will be the use of these methods?

• postorder
• preorder
• inorder

These are already defined in BinaryTreeTraversal in binary_trees.py.

[HarsheetKakar]

@nehasangeetajha can i take over it or are u doing it?

[nehasangeetajha]

@HarsheetKakar u can take this over , i am working on another issue now

[HarsheetKakar]

The main problem I am facing with this particular issue is that since the implementation of tree is done with array, object chaining is very difficult. Something like root.left.left becomes self.tree[self.tree[self.tree[root_idx].left].left] so I am planning to add more properties in ArrayForTrees which might help with this project as well as those to come. All suggestions are welcome.