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属性