红⿊树相关⾯试题
红⿊树和平衡⼆叉树的区别？
红⿊树是⼀个⼆叉查树，不像平衡⼆叉树要求所有节点左右⼦树⾼度差不超过1，红⿊树只要求从⼀个节点到所有叶结点的路径中，最长路径不超过最短路径的两倍，所以红⿊树只追求树的⼤致平衡。
因为对树平衡程度的不同要求，平衡⼆叉树在插⼊和删除的过程中会花费⽐较⼤的代价来维护树的平衡，所以平衡⼆叉树不适合插⼊、删除太多的场景。⽽红⿊树只要求弱平衡，它做到了当插⼊和删除时，只需最多旋转3次就能实现⼀定程度的平衡，所以能将查询、插⼊和删除的时间复杂度维持在对数级别（O(logn)）。
对红⿊树了解吗？说⼀下
先讲上⾯红⿊树与平衡⼆叉树的区别，再讲下⾯的性质。
红⿊树性质：
红⿊树中节点分为⿊⾊节点和红⾊节点。
根节点和所有叶⼦结点（NIL节点）是⿊⾊。
每条从根到叶⼦的路基上不能出现连续两个红⾊节点。
从任⼀节点到所有叶⼦结点的路径上的⿊⾊节点数量相同。
上⾯的性质就保证了从⼀个节点到叶结点的最长路径不会⽐这个节点到叶结点的最短路径⼤两倍。
二叉树的基本性质
树调整规则：红⿊树调整规则的变化对应性质的变化，调整的⽅式也主要是左右旋转。⽐较特殊的有：插⼊⼀个节点时，当⽗节点和叔叔节点都是红⾊的时候，会把⽗节点和叔叔节点的颜⾊变成⿊⾊，然后把祖先节点的颜⾊变成红⾊，之后再继续进⾏判断。
JDK 1.8中HashMap有使⽤到红⿊树，你知道触发条件是什么吗？
当冲突链表的长度超过8并且hash表的长度>=64时，会将链表转换成红⿊树。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。