──────────────────────────────────── ┌————————————┐
│▉▉♥♥♥♥♥♥♥♥ 99

二叉树与红黑树

• 一、前言
• 一、手撕C++
• 二、源码分析
• 三、红黑树叶子节点该怎么判断呢？
• 四、旋转？rotate？
• • 左旋？LeftRotate？
  • 右旋？RightLeft？
• 总结

一、前言

昨天的知识掌握的很好了，主要代码上感觉可以深入研究一下，只是时间不充足，目前这个阶段我自认为还是保持一颗初学者的心态，哈哈，（cosplay没玩过谁）所以不要太急于求成，好吧，开始今天的学学习。

King老师再三强调，每听一节课都应该至少做一个技术博客整理，勉强试试看吧。

**+ 基础组件：以轮子方式实现，它是不能独立运行的。比如：原子操作，队列操作，死锁检测，内存泄漏的组件，分布式锁的实现，libevent，线程池，内存池。

• 中间件 ：mysql单独运行起来的，TiDB，RockDB，Nginx，mongoDB。
• 框架：C++和Java其他语言比起来没有大一统的框架，不同场景有不同的框架。Skynet，Tasrs(腾讯方案)，dpdk。**

阅读源码的能力是基础组件的这块，掌握的好会发现代码都似曾相识。Rust还没有像golang这样的普及，文字乏味些有时候还是蛮让人舒服的。

Rust性能能和C++进行媲美。，但是我昨天刚被授业恩师上了一课，怹很有信心的保证C++能干一辈子，谁会会相信这种论调。本节课是2021年10月21日的事，嘿嘿，过去发生的事要不要放在心上，这事还真不好说。

值得注意的是，零声学院老师的King老师真的是有点君子风范啊，怹老人家已经明确表示批准了学生们可以给怹打广告，这让我感觉到墨子的那一套还真有意思，好吧。
既然这样，那干脆，嘿，瞧一瞧看一看，零声学院的King老师吧，除了教做人之外还能给讲点知识，这样真的有点意思么。用King老师自己的逻辑，无感情无广告。用笔者的语气，没钱白让我帮忙？哼。

一、手撕C++

哦，粗心马虎的恶习看样子要伴随我的终生了。手撕红黑树这是唯独C++程序员可以享有的美味佳肴，JAVA的程序员只能望其项背了。
红黑树红黑树，红黑和色盲没关系，01树也可以的呀。

• 根节点肯定时黑色的，每个叶子节点时黑色的。
• 每个叶子节点时红的，则它的两个儿子都是黑的。
• 红黑树绝不允许出现两个相邻的节点时红色的，那这个红色节点可够金贵的。
• 这句话很重要，平衡的性质所决定的。并非平衡所有的节点，平衡的是黑高，看样子黑色也很重要啊。
  

二、源码分析

对，黑色节点是叶子节点，那我怎么判断谁是叶子节点啊？上代码了，对，这看样子很合理啊。
有一个隐含的条件，实现起来非常重要，嗯，先说重要的，很合理啊。
怎么去判断叶子节点呢。

typedef struct _rbtree_node{unsigned char color;struct _rbtree_node* left;struct _rbtree_node* right;struct _rbtree_node* parent;KEY_TYPE key;void* value;}rbtree_node;**未完成，继续学。**

三、红黑树叶子节点该怎么判断呢？

叶子节点都是黑色的！
左右子树都为空，被称为叶子节点。
有没有叶子节点指向它？

四、旋转？rotate？

二叉树本身就带有旋转，红黑树也只是继承了红黑树的旋转。
换句话说，旋转并非二叉树的专利。
如果没有旋转那就不能构成红黑树了！You know？真的挺重要的！

左旋？LeftRotate？

右旋？RightLeft？

明明就是2个东西，一个父节点一个子节点，为啥要搞出这么多名堂？总共5根线，3根线对不对？2节点，变化1次。

void _left_rotate(_rbtree* T, _rbtree_node* x){rbtree_node* y = x->right;//onex->right = y->left;y->left = x->left;if (y->left != T->nil){y->left != T->nil;y->left->parent;}//twoy->parent = x->parent;if (x->parent == T->nil){T->root = y;}else if (x==x->parent->left){x->parent->left = y;}else{x->parent->right = y;}//threey->left = x;x->parent = y;}

感悟：右子树函数其实和左子树函数类似，只是x和y，left和right对换就好。
奇怪，左旋右旋能和颜色没关系？滑天下之大稽。

总结

想想这样公开零声的知识，不太可能侵犯了人家的知识产权，惭愧~
好在King老师高风亮节，怹也并不想计较这些，但是我这么耿直的boy，尴尬不。

• 确实是这样，King老师认为自己整理的笔记还是应该分享一部分，这也许会是一个好的学习习惯。
• ennn，搞笑，没有证据的道理也能让我信服，滑天下之大稽。
• 这几句是我写的？难以置信。
• 博客这个东西以后坚持凑合写吧，本人的脑瓜子还用这？2004期居然有个学员才总结了40-50次课，整理了最多300页的笔记，就这样也能拿到腾讯的offer。
• 依我的高见，别跟我提什么热爱，自律坚持这都是自找的，他写这么多文章这种行为十分令本公子厌恶。这种货色也配让King老师这样的人物如此高调地拿出来炫耀，不可能被外国友人笑掉大牙吧，我真得是为King老师的名声担忧啊。
• 开通github，维护github，不喜欢开源还不喜欢奖学金吗嘿嘿，这件事看样子今天就得办啦。得把自己的代码放在github，这样可以互相分享，可是我的代码这么金贵，我是真舍不得拿出来让别人看到呀，还是无法跨越自己污浊心灵上宽广莫大的鸿沟。

课上到这里，这里是课程开始的26分钟28秒，个人感觉老师搞得我平静的内心还真有点烦躁了，罗里吧嗦的还讲不讲知识了，毕竟早上的时间那么宝贵，都是花重金求知识的，我这么温柔的谦谦君子都有点看不过去了。怹老人家此时就像奶妈附体。想想还是应该给King老师一点点面子，毕竟出来混都是要面子的人。得，这口奶小生凑合吃了。
后来，老师又提到了关系，说跟他关系好的混的基本都不差。这都21世纪了还搞人情那一套，德云社是属于全体演员和观众哒嘎嘎！他特别强调了，不要太看重所谓的礼节，今天对King老师也算有点佩服了，嗯，加油吧King老师。
今天想想，说话真的太太太太简单了，自己学了两天就会了，这有啥啊。我一个圣人君子，很在乎别人对我的评价的呀。想想我这半辈子，上大学的时候知识没学着。胸怀大志的奔赴社会上闯荡，最后钱也赚到，哈哈哈想想就觉得搞笑。
最后，突然之间想借用孟非老师的人生哲理：天道酬勤，随遇而安。