RBT问答面试题及参考答案

问：有了二叉搜索树，为什么还需要平衡二叉树？

二叉搜索树容易退化成一条链

这时，查找的时间复杂度从O ( log n）也将退化成O ( N )

引入对左右子树高度差有限制的平衡二叉树 AVL，保证查找操作的最坏时间复杂度也为O ( log n）

问：有了平衡二叉树，为什么还需要红黑树？

AVL的左右子树高度差不能超过1，每次进行插入/删除操作时，几乎都需要通过旋转操作保持平衡

在频繁进行插入/删除的场景中，频繁的旋转操作使得AVL的性能大打折扣

红黑树通过牺牲严格的平衡，换取插入/删除时少量的旋转操作，

整体性能优于AVL

• 红黑树插入时的不平衡，不超过两次旋转就可以解决；删除时的不平衡，不超过三次旋转就能解决
• 红黑树的红黑规则，保证最坏的情况下，也能在O ( log n）时间内完成查找操作。

问：红黑树那几个原则，你还记得么？

可以按照括号里边的分类，记住 红黑树的几个原则：

• （颜色属性）节点非黑即红
• （根属性）根节点一定是黑色
• （叶子属性）叶子节点（NIL）一定是黑色
• （红色属性）每个红色节点的两个子节点，都为黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
• （黑色属性）从任一节点到其每个叶子的所有路径，都包含相同数目的黑色节点。

问：红黑树写入操作 ，是如何找到它的父节点的？

红黑树的节点 TreeNode它就是继承Node结构，

先看看红黑树的节点结构

以HashMap中的红黑树的结构定义为例子：

  static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        volatile V val;
        volatile Node<K,V> next;
        }


/**
 * Nodes for use in TreeBins
 */
static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // red-black tree links
    TreeNode<K,V> left;
    TreeNode<K,V> right;
    TreeNode<K,V> prev;    // needed to unlink next upon deletion
    boolean red;

    TreeNode(int hash, K key, V val, Node<K,V> next,
             TreeNode<K,V> parent) {
        super(hash, key, val, next);
        this.parent = parent;
    }

TreeNode在Node基础上加了几个字段，分别指向父节点parent，然后指向左子节点left，还有指向右子节点的right，

然后还有表示颜色red属性

红黑树的插入操作：

首先是找到一个合适的插入点，就是找到插入节点的父节点，

由于红黑树 它又满足BST二叉查找树的 有序特性，这个找父节点的操作和二叉查找树是完全一致的。

二叉查找树，左子节点小于当前节点，右子节点大于当前节点，

然后每一次向下查找一层就可以排除掉一半的数据，查找的效率在log(N)

最终查找到nil节点或者 key一样的节点。

如果最终查找到 key一样的节点，进行更新操作。这个TreeNode.key 与当前 put.key 完全一致。这就不需要插入，替换value就可以了，父节点就是当前节点的父节点

如果最终查找到nil节点，进行插入操作。nil节点的父节点，就是当前节点的父节点，把插入的节点替换nil节点。然后进行红黑树的 平衡处理。

问：红黑树的有那些内部操作

变色

把一个红色的节点变成黑色，或者把一个黑色的节点变成红色，就是对这个节点的变色。

旋转

与平衡二叉树的旋转操作类似。