最近，看 HashMap 的时候，看到了其中的实现用到了红黑树。于是就想来复习一下，老久以前学的东西差不多都忘掉了。 红黑树的本质是二叉搜索树，它的约束条件更多而已。这篇复习笔记首先过一下二叉搜索树，然后再进入红黑树。BS

在互联网职场论坛，一位职场人发帖吐槽到。字节跳动面试真的是太无聊了，不知道你们工作中哪里需要手撕AVL和红黑树，哪里需要把指针移动来移动去的。个人觉得聪明和背题是两回事，字节面试对你的工作经验和业务丝毫不关心，去面试，代码没让写，但是让总结

红黑树（Red Black Tree） 是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary