红黑树的定义是什么？底层原理是什么？ [ 新手入门 ]

红黑树是一种自平衡的二叉搜索树，它满足以下五个性质：

每个节点要么是红色，要么是黑色。

根节点是黑色的。

每个叶子节点（NIL节点，空节点）都是黑色的。

如果一个节点是红色的，则它的两个子节点都是黑色的。

对于每个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点（即具有相同的黑色深度）。

红黑树的底层原理是通过不断进行节点插入、删除和调整颜色来保持树的平衡，以确保树的高度为 O(log n) 级别，其中 n 表示树中节点的数量。为了保证这一点，红黑树中的每个节点除了包含存储的键值和关联数据之外，还包含一个颜色属性，用于表示节点的颜色，一般为红色或黑色。

在插入新节点的时候，需要根据二叉搜索树的规则找到合适的位置插入节点，并将节点的颜色设置为红色。然后需要对树进行调整来保持红黑树的五个性质。具体来说，可能需要进行以下三种调整：

改变节点的颜色：将一个红色节点的颜色变为黑色，或将一个黑色节点的颜色变为红色。

左旋转：针对节点的右子节点比左子节点高，将该节点向左旋转，使得原节点的右子节点变成新子树的根节点，原节点变为新子树的左子节点。

右旋转：针对节点的左子节点比右子节点高，将该节点向右旋转，使得原节点的左子节点变成新子树的根节点，原节点变为新子树的右子节点。

这三种调整操作可以逐级向上进行，直到根节点为止。通过这种调整，红黑树可以始终保持平衡，而且具有比 AVL 树更好的性能，被广泛用于高效的数据存储和搜索算法中。