面试让我手写红黑树 _红黑树

作者：小傅哥
博客：https://bugstack.cn

沉淀、分享、成长，让自己和他人都能有所收获！

一、前言：挂在树上！不知道你经历过HashMap的夺命连环问！
为啥，面试官那么喜欢让你聊聊 HashMap？因为 HashMap 涉及的东西广，用到的数据结构多，问题延展性好，一个 HashMap 就能聊下来80%的数据结构了。而且面试 HashMap 能通过你对红黑树的了解定位出你哪个级别的研发人员。
而红黑树的知识点可以说是非常庞大，在学习红黑树时也不能一下就能掌握，甚至很程序员压根就没搞明白红黑树，只是背下来它的几条限定规则而已。
其实一开始我也是这样！不过总感觉这块的知识点不搞个明明白白，就闹心。因为不可能一个理科的东西，是需要死记硬背搞下来的。所以在翻阅资料、文档、历史、典籍，找到红黑树的演化过程，它是从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. 二叉搜索树结构实现
二叉搜索树是整个树结构中最基本的树，同时也是树这个体系中实现起来最容易的数据结构。但之所以要使用基于二叉搜索树之上的其他树结构，主要是因为使用数据结构就是对数据的存放和读取。那么为了提高吞吐效率，则需要尽可能的平衡元素的排序，体现在树上则需要进行一些列操作，所以会有不同的结构树实现。
而实现二叉搜索树是最好的基础学习，了解基本的数据结构后才更容易扩展学习其他树结构。

源码地址：https://github.com/fuzhengwei/java-algorithms
本章源码：https://github.com/fuzhengwei/java-algorithms/tree/main/data-structures/src/main/java/tree

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; }