C언어에 익숙해지랴, 당장 C언어로 RB Tree를 구현하랴 마음이 급해서 우선 ChatGPT와 대화하며 RB Tree의 개념이 익숙해져보기로 했다. 설명을 나름 잘 해주고 내가 특정하게 궁금한 점들을 직접 물어볼 수 있어서 좋았다. 다만 중간중간 이상하게 설명하는 부분들은 내가 걸러서 이해할 수 있어야 한다. 도움은 되었다고 생각하지만 결국 Introduction to Algorithms 책을 통해 바로 공부하고 구현하는게 가장 빨랐을 것 같다..

Red-Black Tree Rules

In a red-black tree, each node is either red or black. The rules for coloring nodes are as follows:

1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

These rules ensure that the red-black tree is balanced and that the longest path from the root to any leaf is no more than twice as long as the shortest path. Therefore, the height of a red-black tree is O(log n), where n is the number of nodes in the tree.

To summarize, a node in a red-black tree is colored black if it is a root node or a leaf node, or if it has a red parent. A node is colored red if it has a black parent and its children are both black.

Maintaining balance when inserting nodes

When inserting a node into a red-black tree, you need to perform the following steps to maintain the balance of the tree:

1. Insert the node as you would in a normal binary search tree.
2. Color the node red.
3. If the parent of the node is also red, then you need to perform a color flip to maintain the balance. This involves coloring the parent black and its siblings black, while coloring the grandparent red. You then check if the grandparent violates any of the red-black tree properties. If it does, you need to repeat this step on the grandparent.
4. If the parent of the node is black, then the tree is still valid, and you don't need to do anything else.
5. If the node is the root of the tree, you must color it black to maintain property 1.

These steps ensure that the red-black tree maintains the properties of red-black tree which guarantee that the tree is balanced, and the height of the tree is O(log n), where n is the number of nodes in the tree.

1. The usual steps to insert a node into a binary search tree

To insert a node into a binary search tree, you can follow these steps:

1. Start at the root of the tree.
2. If the tree is empty, create a new node and make it the root of the tree.
3. Compare the value of the node you want to insert with the value of the current node.
4. If the value is less than the current node's value, move to the left subtree and repeat the process from step 3.
5. If the value is greater than the current node's value, move to the right subtree and repeat the process from step 3.
6. If you encounter a NULL pointer, create a new node with the value you want to insert and attach it to the parent node at the NULL pointer.

Note that in a binary search tree, the values in the left subtree of a node are always less than its value, and the values in the right subtree are always greater. This property allows you to efficiently search for a node in the tree and is the basis for many operations in the binary search tree data structure, including insertion, deletion, and search.

After inserting a node into the binary search tree, you may need to rebalance the tree to ensure that it remains height-balanced, but this is not necessary for a normal binary search tree as it doesn't have the additional constraints of a red-black tree.

2. Why is the node being inserted colored red?

The reason why the node that you insert in a red-black tree is initially colored red is to ensure that the tree remains balanced.

By coloring the new node red, we ensure that it doesn't break the black depth property (property 4), which requires that all paths from the root to the leaves must have the same number of black nodes. If we inserted a black node instead, the black depth of one or more paths would increase, violating the property.

So, by inserting a red node, we allow the black depth of the paths to remain the same, and we can fix any violations of the other properties using color changes and rotations. The red color also helps to indicate that the node may need to be adjusted to maintain the balance of the tree.

Note that after the insertion of a new node and any necessary rotations and color changes, the red-black tree may not be perfectly balanced, but it will still be relatively balanced and satisfy all the red-black tree properties.

3. Color fliping parent's sibling and grandparents

Why filp parent's siblings?

Remember that the red-black tree properties require that every simple path from a node to a descendant leaf contains the same number of black nodes (property 4). When you color the parent, its sibling, and its grandparent during a color flip, you are essentially moving the red node up one level in the tree while preserving the black height of the subtrees below it.

In other words, the subtree rooted at the sibling node still has the same black height as it did before the color flip, because we haven't changed anything about its structure or the number of black nodes on any of its paths to descendant leaves. Similarly, the black height of the inserted subtree is still the same, because we haven't changed anything about its structure or the number of black nodes on any of its paths to descendant leaves.

So, the black height of the inserted subtree and the sibling's subtree remain the same after a color flip, and the red-black tree properties continue to hold.

Why flip grandparent?

The reason for coloring the grandparent node red is to ensure that the red-black tree remains balanced, even after future insertions.

If the newly added node is the left child of a left child or the right child of a right child, then it creates a "double red" violation, which needs to be fixed by recoloring and rotating the nodes. On the other hand, if the newly added node is the left child of a right child or the right child of a left child, then it creates a "single red" violation that can be fixed by recoloring without rotation.

By coloring the grandparent node red in both cases, the red-black tree is ensuring that the double red and single red violations are handled in the same way. This simplifies the code for insertions and ensures that the tree remains balanced regardless of the pattern of insertions.

Rotations

When we do a left rotation on a node x, we assume that its right child(y) is not nil. x may be any node in the tree whose right child is not nil.
left rotation piviots around the link from x to y. it makes y the new root of the subtree, with x as y's left child and y's left child as x's right child