RBT问答面试题及参考答案

图片[1]-RBT问答面试题及参考答案-不念博客
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节点。然后进行红黑树的 平衡处理。

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

变色

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

旋转

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

------本页内容已结束,喜欢请分享------
© 版权声明
THE END
喜欢就支持一下吧
点赞129赞赏 分享
评论 抢沙发
头像
欢迎光临不念博客,留下您的想法和建议,祝您有愉快的一天~
提交
头像

昵称

取消
昵称表情代码图片

    暂无评论内容