如何理解红黑树和左右旋转的性质？

告诉我红黑树的性质以及它们的左右旋转。

参考答案：

检验点：算法

公司：京东、阿里巴巴

1）平衡二叉树（AVL树）：

红黑树是基于红黑树提出的- 黑树树。

平衡二叉树，又称AVL树，是一种特殊的二叉排序树。左右子树都是平衡二叉树，左右子树的高度差的绝对值不超过1。

树中左右子树的高度差的绝对值AVL 树中所有作为根的节点不超过 1。

二叉树节点中左子树的深度减去右子树的深度的值称为平衡因子 BF。那么平衡二叉树上所有节点的平衡因子只能是-1、0、1。只要二叉树中某个节点的平衡因子绝对值大于1，则该二叉树是不平衡的。

2）红黑木：

红黑木是在AVL木的基础上发展起来的。红黑树是二叉搜索树，只不过每个节点都增加了一个存储位来表示该节点的颜色，可以是红也可以是黑（要么红，要么黑）。通过限制从根到叶子的任何路径上每个节点的着色方式，红黑树确保没有路径的长度是任何其他路径的两倍。因此，就要求而言，红黑树是一种弱平衡二叉树。对于严格的AVL树，旋转次数较少，因此当查找、插入和删除操作较多时，通常使用红黑树。

特点：

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

2。根节点为黑色；

3。每个叶子节点（叶子节点为NULL指针或树尾的NULL节点）全部为黑色；

4。如果一个节点是红色的，那么它的子节点必须是黑色的。

5。对于任意节点，到叶子点树的NULL指针的每条路径都包含相同数量的黑色节点；

从根到叶子的最长可能路径不超过最短可能路径。两倍长。它可以在 O(log n) 时间内搜索、插入和删除，其中 n 是树中元素的数量。恢复红黑属性需要小的 (O(log n)) 颜色变化（实际上非​​常快）和不超过 3 次树旋转（两次用于插入）。这意味着插入和删除可以保持O(log n)次，

3）红黑树相对于AVL树的优点：

AVL树高度平衡，频繁的插入和删除会导致频繁的重新平衡。这导致效率降低；红黑树不是很平衡，被认为是一种折衷方案。它最多可以插入两个旋转，最多删除三个旋转。

所以红黑树查找、插入、删除的性能都是O(logn)，而且性能稳定，所以STL中很多结构，包括maps的底层实现，都使用红黑树。

4）红黑树旋转：

旋转：红黑树的旋转是搜索树的局部操作，可以保持二叉搜索树的属性。有两种旋转类型：左旋和右旋。通过改变树中某些节点的颜色和指针结构，在插入和删除操作后保持红黑树的红黑特性。

左旋转：对节点x进行左旋转操作时，假设其右子节点为y：以x到y的链条为“支点”。设 y 为子树的新根节点，x 为 y 的左子节点，y 的左子节点为 x 的右子节点。

右旋转：对节点x进行右旋转操作时，假设其左子节点为y：以x到y的链为“支点”。设 y 为子树的新根节点，x 为 y 的右子节点，y 的右子节点为 x 的左子节点。