首页 > 其他分享 >35+，如果面试让我手写红黑树！

35+，如果面试让我手写红黑树！

时间：2022-11-06 15:34:04浏览次数：78  
标签：Node node parent tree 35 ----- 红黑树 手写 节点

一、前言：挂在树上！

不知道你经历过HashMap的夺命连环问！

为啥，面试官那么喜欢让你聊聊 HashMap？因为 HashMap 涉及的东西广，用到的数据结构多，问题延展性好，一个 HashMap 就能聊下来80%的数据结构了。而且面试 HashMap 能通过你对红黑树的了解定位出你哪个级别的研发人员。

file

而红黑树的知识点可以说是非常庞大，在学习红黑树时也不能一下就能掌握，甚至很程序员压根就没搞明白红黑树，只是背下来它的几条限定规则而已。

其实一开始我也是这样！ 不过总感觉这块的知识点不搞个明明白白，就闹心。因为不可能一个理科的东西，是需要死记硬背搞下来的。所以在翻阅资料、文档、历史、典籍，找到红黑树的演化过程，它是从2-3树演变而来，而2-3树、AVL树，这类B-树，也就是 BalancedTree 平衡树。它们都是为了解决 BST 二叉搜索树不自平衡而来的产物。

那么现在清楚了，要想搞定红黑树，让懂了就是真的懂，就需要把前面这些知识搞定，并且除了理论还能用落地的案例代码编写出来，才是悟透。好，那么接下来，小傅哥就带着你一起搞定这点事

二、BST 树

Binary Search Tree历史

二叉搜索树算法是由包括 PF Windley、Andrew Donald Booth、Andrew Colin、Thomas N. Hibbard 在内的几位研究人员独立发现的。该算法归功于 Conway Berners-Lee 和 David Wheeler ，他们在 1960 年使用它在磁带中存储标记数据。 最早和流行的二叉搜索树算法之一是 Hibbard 算法。

1. 二叉搜索树数据结构

二叉搜索树（Binary Search Tree），也称二叉查找树。如果你看见有序二叉树（Ordered Binary tree）、排序二叉树（Sorted Binary Tree）那么说的都是一个东西。

二叉树

  • 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 任意节点的左、右子树也分别为二叉查找树；

二叉搜索树在日常开发中使用的场景还是比较多的，例如基于组合模式实现的规则引擎，它就是一颗二叉搜索树。但类似这样的开发中用到的二叉树场景，都是基于配置生成，所以组合出来的节点也更加方便控制树高和平衡性。这与 Java API HashMap 中的红黑树这样为了解决插入节点后仍保持树的平衡性是有所不同的。

所以二叉搜索树也是一颗没有经过调衡的基础性数据结构，在一定概率上它完成有可能退化成链表，也就是从近似O(logn)的时间复杂度退化到O(n)。关于二叉搜索树的平衡解决方案，包括；AVL树、2-3树、红黑树等，小傅哥会在后续的章节继续实现。

2. 二叉搜索树结构实现

二叉搜索树是整个树结构中最基本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构，主要是因为使用数据结构就是对数据的存放和读取。那么为了提高吞吐效率，则需要尽可能的平衡元素的排序，体现在树上则需要进行一些列操作，所以会有不同的结构树实现。

而实现二叉搜索树是最好的基础学习，了解基本的数据结构后才更容易扩展学习其他树结构。

2.1 树枝定义

public Integer value;
public Node parent;
public Node left;
public Node right;
  • 用于组成一颗树的节点，则需要包括；值和与之关联的三角结构，一个父节点、两个孩子节点。如果是AVL树还需要树高，红黑树还需要染色标记。

2.2 插入节点

public Node insert(int e) {
    if (null == root) {
        root = new Node(e, null, null, null);
        size++;
        return root;
    }
    
    // 索引出待插入元素位置，也就是插入到哪个父元素下
    Node parent = root;
    Node search = root;
    while (search != null && search.value != null) {
        parent = search;
        if (e < search.value) {
            search = search.left;
        } else {
            search = search.right;
        }
    }
    
    // 插入元素
    Node newNode = new Node(e, parent, null, null);
    if (parent.value > newNode.value) {
        parent.left = newNode;
    } else {
        parent.right = newNode;
    }
    size++;
    return newNode;
}
  • 首先判断插入元素时候是否有树根，没有则会把当前节点创建出一颗树根来。
  • 如果当前树是有树根的，则对插入元素与当前树进行一个节点遍历操作，找到元素可以插入的索引位置 parent（挂到这个父节点下）。也就是 search 搜索过程。
  • 最后就是插入元素，通过给插入值创建一个 Node 节点，并绑定它的父元素，以及把新元素挂到索引到的 parent 节点下。

2.3 索引节点

public Node search(int e) {
    Node node = root;
    while (node != null && node.value != null && node.value != e) {
        if (e < node.value) {
            node = node.left;
        } else {
            node = node.right;
        }
    }
    return node;
}
  • 值查找的过程，就是对二叉搜索树的遍历，不断的循环节点，按照节点值的左右匹配，找出最终相当的值节点。

2.4 删除节点

public Node delete(int e) {
    Node delNode = search(e);
    if (null == delNode) return null;
    return delete(delNode);
}

private Node delete(Node delNode) {
    if (delNode == null) return null;
    Node result = null;
    if (delNode.left == null) {
        result = transplant(delNode, delNode.right);
    } else if (delNode.right == null) {
        result = transplant(delNode, delNode.left);
    } else {
        // 因为删除的节点，有2个孩子节点，这个时候找到这条分支下，最左侧做小的节点。用它来替换删除的节点
        Node miniNode = getMiniNode(delNode.right);
        if (miniNode.parent != delNode) {
            // 交换位置，用miniNode右节点，替换miniNode
            transplant(miniNode, miniNode.right);
            // 把miniNode 提升父节点，设置右子树并进行挂链。替代待删节点
            miniNode.right = delNode.right;
            miniNode.right.parent = miniNode;
        }
        // 交换位置，删除节点和miniNode 可打印测试观察；System.out.println(this);
        transplant(delNode, miniNode);
        // 把miniNode 提升到父节点，设置左子树并挂链
        miniNode.left = delNode.left;
        miniNode.left.parent = miniNode;
        result = miniNode;
    }
    size--;
    return result;
}
private Node getMinimum(Node node) {
    while (node.left != null) {
        node = node.left;
    }
    return node;
}

private Node transplant(Node delNode, Node addNode) {
    if (delNode.parent == null) {
        this.root = addNode;
    }
    // 判断删除元素是左/右节点
    else if (delNode.parent.left == delNode) {
        delNode.parent.left = addNode;
    } else {
        delNode.parent.right = addNode;
    }
    // 设置父节点
    if (null != addNode) {
        addNode.parent = delNode.parent;
    }
    return addNode;
}
2.4.1 删除单节点

img

  • 待删除节点14，判断此节点的父节点的孩子节点，哪个等于14，找出左右
  • 把待删节点的右孩子节点，挂到删除节点的右节点
  • 给待删节点的右孩子节点，设置上父节点
2.4.2 删除双节点

删除节点

  • 待删除节点64，含有双子节点，则需要根据第一个右子节点查找最小左子节点。从89到72，如果有比72还小的左子节点，继续排查。
  • 排查到节点72，将72这个准备替换待删元素的节点，与右子节点73进行位置交换，过程与 4.1 相同。使用交换函数 transplant
  • 最后是进行节点72与待删节点64的交换过程，更换三角关系，父节点、左子节点、右子节点。

3. 二叉搜索树功能测试

为了方便观察树结构的变化，这里小傅哥找了一些资料资料，一种是我们可以通过程序来打印（类似大家之前打印99乘法表，另外是使用线上的可视化图：https://visualgo.net/zh/bst?slide=1）

3.1 随机插入元素

@Test
public void test_binary_search_tree() {
    BinarySearchTree tree = new BinarySearchTree();
    for (int i = 0; i < 10; i++) {
        tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

测试结果

         /----- 91
         |       \----- 78
 /----- 74
 |       \----- 67
61
 |       /----- 51
 \----- 40
         |       /----- 28
         \----- 14
                 \----- 7
                 
Process finished with exit code 0
  • 因为你测试时的随机数不同，可能会出现很多不同结构的二叉搜索树，也可能是一个类似链表结构的退化树。

3.2 插入并且删除

@Test
public void test_insert_delete(){
    BinarySearchTree tree = new BinarySearchTree();
    tree.insert(32);
    tree.insert(7);
    tree.insert(64);
    tree.insert(63);
    tree.insert(89);
    tree.insert(72);
    tree.insert(94);
    tree.insert(6);
    tree.insert(14);
    tree.insert(18);
    tree.insert(73);
    System.out.println(tree);
    
    // 删除单节点，只有一个孩子的父节点
    // tree.delete(14);
    
    // 删除双节点，拥有二个孩子的父节点
    tree.delete(64);
    System.out.println(tree);
}

测试结果

                 /----- 94
         /----- 89
         |       |       /----- 73
         |       \----- 72
 /----- 64
 |       \----- 63
32
 |               /----- 18
 |       /----- 14
 \----- 7
         \----- 6

                 /----- 94
         /----- 89
         |       \----- 73
 /----- 72
 |       \----- 63
32
 |               /----- 18
 |       /----- 14
 \----- 7
         \----- 6


Process finished with exit code 0
  • 这个案例就是 删除双节点 的案例，删除了节点64以后，节点72被提取上来使用。读者伙伴也可以尝试删除其他节点测试验证

三、AVL 树

AVL树历史

在计算机科学中，AVL 树以其两位苏联发明家Georgy Adelson-Velsky和 Evgenii Landis的名字命名，他们在 1962 年的论文“信息组织算法”中发表了它。它是一种自平衡二叉搜索树(BST)，这是发明的第一个这样的数据结构。

1. AVL树数据结构

AVL 自平衡二叉树的出现，其目的在于解决二叉搜索树退化成链表的问题。当我们向BST二叉搜索树顺序存入1、2、3、4、5、6、7个元素时，它会退化成一条链表，因而失去树查询的时间复杂度，所以我们需要AVL树平衡树高。如图所示

AVL 那么AVL树是怎么平衡树高的呢？

当二叉树的左右分支树高差不为1时，需要进行左旋或者右旋，来调衡树高。这有点像开车的时候，如果车头偏左就往右打方向盘，车头偏右就往左打方向盘是一个道理。那这个方向盘(左旋、右旋)是怎么打的呢，主要分以下四种情况；

左旋（新增节点6） 右旋（新增节点1） 左旋+右旋（新增节点4） 右旋+左旋（新增节点3）
img img img img
条件：节点4，平衡因子为-2，左旋 条件：节点3，平衡因子为2，右旋 条件：节点3，平衡因子为2，右旋。但当节点2平衡因子-1先左旋。 条件：节点2，平衡因子为-2，左旋。但当节点5平衡因子1先右旋。

2. AVL树代码实现

对于 AVL 树的实现与 BST 二叉搜索树相比，在树的节点定义上多了一个树高的属性。也有些AVL树使用的是平衡因子的属性，就是通过树高计算后的结果。树节点代码结构如下；

public class Node {

    public Class<?> clazz;
    public Integer value;
    public Node parent;
    public Node left;
    public Node right;
    // AVL 树所需属性
    public int height;
    
}

接下来小傅哥就分别通过代码讲解下一颗AVL树的左旋、右旋、左旋+右旋、右旋+左旋的代码操作。不要担心这没有多复杂，只要你能搞清楚左旋，就能搞清楚右旋。两旋弄懂组合就没啥难度了。

2.1 左旋

图解左旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

左旋

代码实现

protected Node rotateLeft(Node node) {
    Node temp = node.right;
    temp.parent = node.parent;
  
    node.right = temp.left;
    if (node.right != null) {
        node.right.parent = node;
    }
  
    temp.left = node;
    node.parent = temp;
  
    if (temp.parent == null) {
        root = temp;
    } else {
        if (temp.parent.left == node) {
            temp.parent.left = temp;
        } else {
            temp.parent.right = temp;
        }
    }
    return temp;
}
  1. 左旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。
  2. 通过节点4拿到父节点2和右子节点5，把父节点2和右子节点5建立关联
  3. 节点5的左子节点，相当于是大于4小于4的那么一个值，只不过这里不体现。那么这个节点4的左子节点，应该被迁移到节点3的右子节点上。
  4. 整理节点5的关系，左子节点为4。左子节点4的父节点为5
  5. 如果说迁移上来的节点5无父节点，那么它就是父节点 root = temp
  6. 迁移上来的节点5，找到原节点4是对应父节点的左子节点还是右子节点，对应的设置节点5的左右位置

2.2 右旋

图解右旋操作；它就是一种摘链更换调整节点的处理过程，小傅哥把它分解展示，整个过程如下；

右旋

代码实现

protected Node rotateRight(Node node) {
    Node temp = node.left;
    temp.parent = node.parent;
    node.left = temp.right;
    if (node.left != null) {
        node.left.parent = node;
    }
    temp.right = node;
    node.parent = temp;
    if (temp.parent == null) {
        root = temp;
    } else {
        if (temp.parent.left == node) {
            temp.parent.left = temp;
        } else {
            temp.parent.right = temp;
        }
    }
    return temp;
}
  1. 右旋的作用，相当于通过向上迁移树高差大于1的右子节点来降低树高的操作。
  2. 通过节点3拿到父节点4和左子节点2，把父节点7和左子节点2建立关联
  3. 节点2的右子节点，相当于是大于2小于3的那么一个值，只不过这里不体现。那么这个节点2的右子节点，应该被迁移到节点3的左子节点上。
  4. 整理节点2的关系，右子节点为3。右子节点3的父节点为2
  5. 如果说迁移上来的节点2无父节点，那么它就是父节点 root = temp
  6. 迁移上来的节点2，找到原节点3是对应父节点的左子节点还是右子节点，对应的设置节点2的左右位置

2.3 左旋 + 右旋

之所以会有左旋 + 右旋，是因为一次右旋操作没法平衡树高，而这种树的不平衡节点的左子节点的右子节点过长，所以要把不平衡节点的左子节点向左旋转一次，之后再进行右旋操作。

左旋+右旋

代码实现

if (factor(node.left) >= 0) {
    Node temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
} else {
    Node temp = super.rotateLeft(node.left);
    refreshHeight(temp.left);
    refreshHeight(temp);
    node.left = temp;
    
    temp = super.rotateRight(node);
    refreshHeight(temp.right);
    refreshHeight(temp);
}

2.4 右旋 + 左旋

之所以会有右旋 + 左旋，是因为一次左旋操作没法平衡树高，而这种树的不平衡节点的右子节点的左子节点过长，所以要把不平衡节点的右子节点向右旋转一次，之后再进行左旋操作。

右旋 + 左旋

代码实现

if (factor(node.right) <= 0) {
    Node temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
} else {
    Node temp = super.rotateRight(node.right);
    refreshHeight(temp.right);
    refreshHeight(temp);
    node.right = temp;
    
    temp = super.rotateLeft(node);
    refreshHeight(temp.left);
    refreshHeight(temp);
}

3. AVL树功能测试

为了验证AVL树的实现正确与否，这里我们做一下随机节点的插入，如果它能一直保持平衡，那么它就是一颗可靠 AVL 平衡树。

单元测试

@Test
public void test_random() {
    AVLTree tree = new AVLTree();
    for (int i = 0; i < 30; i++) {
        tree.insert(new Random().nextInt(100));
    }
    System.out.println(tree);
}

测试结果

输入节点：61,3,34,82,1,75,56,65,87,18,3,96,53,50,42,24,69,11,95,69,1,1,84,22,5,70,28,55,38,92

                         /----- 96(0)
                 /----- 95(1)
                 |       \----- 92(0)
         /----- 87(2)
         |       |       /----- 84(0)
         |       \----- 82(1)
 /----- 75(3)
 |       |               /----- 70(0)
 |       |       /----- 69(1)
 |       \----- 69(2)
 |               \----- 65(0)
61(5)
 |               /----- 56(1)
 |               |       \----- 55(0)
 |       /----- 53(2)
 |       |       |       /----- 50(0)
 |       |       \----- 42(1)
 |       |               \----- 38(0)
 \----- 34(4)
         |                       /----- 28(0)
         |               /----- 24(1)
         |               |       \----- 22(0)
         |       /----- 18(2)
         |       |       \----- 11(1)
         |       |               \----- 5(0)
         \----- 3(3)
                 |       /----- 3(1)
                 |       |       \----- 1(0)
                 \----- 1(2)
                         \----- 1(0)


Process finished with exit code 0
  • 随机插入30个节点，每个节点的顺序已经打印，经过AVL左右旋调衡后，二叉结构始终保持树高平衡因子不超过1，那么验证通过。

四、2-3树

这时候大部分资料会用2-3树来讲解红黑树，不过又不去实现一个2-3树，只是用了一个理论套另外一个理论。虽然能从理解上多一些参考，但始终感觉没有抓手呀。对于理科思维来说，你得给我东西呀。老是整这悬得楞的

标签：Node,node,parent,tree,35,-----,红黑树,手写,节点
From： https://blog.51cto.com/u_15720252/5827267

相关文章

  • 计算机等级考试二级C语言上机题集（第31~35套）
    第31套1．程序填空题给定程序中，函数fun的功能是：有N*N矩阵，将矩阵中的外围元素顺时针旋转。操作顺序是：首先将第1行元素值存入临时数组r，然后使第1列成为第1行，最后1行成为第1列......
  • RK3568+鸿蒙教学实验平台鸿蒙认证设计方案
    RK3568/3288/3399+鸿蒙系统，广泛应用于工业平板/军工医疗等信创产业，支持软硬件定制！不仅搭载国产化系统，颜值在线，而且接口丰富，核心功能强劲，配套10.1寸液晶显示屏应用场景包括：智......
  • 35、Java——一个案例学会Dao+service层对数据表的增删改查
    ✅作者简介：热爱国学的Java后端开发者，修心和技术同步精进。文章目录​​案例​​​​建表​​​​配置​​​​Animal类​​​​DBUtils数据库工具类​​​​DateUtils日期......
  • webpack : 无法加载文件 C:\Users\13573\AppData\Roaming\npm\webpack.ps1,因为
    问题：C:\Users\XXX\AppData\Roaming\npm\webpack.ps1因为在此系统上禁止运行脚本管理员输入  set-ExecutionPolicyRemoteSigned  回车输入A或者Y即可解决 ......
  • webpack : 无法加载文件 C:\Users\13573\AppData\Roaming\npm\webpack.ps1,因为
    问题：C:\Users\XXX\AppData\Roaming\npm\webpack.ps1因为在此系统上禁止运行脚本管理员输入  set-ExecutionPolicyRemoteSigned  回车输入A或者Y即可解决 ......
  • 【面试题】 面试手写JS 十六题（必看）
     1、手写实现防抖和节流1.1实现防抖函数防抖函数原理：把触发非常频繁的事件合并成一次去执行 在指定时间内只执行一次回调函数，如果在指定的时间内又触发了该事件，则回调函......
  • P3521 [POI2011]ROT-Tree Rotations
    P3521[POI2011]ROT-TreeRotations分析我们看操作，我们可以将任意一个节点的左右子树交换。则，我们是改变的一段序列的顺序。这里类似于的归并排序求逆序对的过程。对于......
  • 红黑树原理
    红黑树（RedBlackTree）是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。性质节点是红色或黑色。根节点是黑色。每个叶子节点（NIL）是黑色......
  • 教你手写webpack常用loader
    前言webpack作为目前主流的前端构建工具，我们几乎每天都需要与它打交道。个人认为一个好的开源产品壮大的原因应该包括核心开发者的稳定输出以及对应生态的繁荣。对于生态......
  • 手写一个webpack插件
    前言前端性能优化是一个老生常谈的话题，关于性能优化的技术文档和书籍都特别多。如果大家想深入学习前端性能优化相关内容，有以下推荐雅虎军规35条某东上搜“前端性能优......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99