終於在工作中實際用到了紅黑樹 - 交易所配對引擎

首先了解紅黑樹跟一般的二分查找樹的區別可以看下面連結中的漫畫，清楚明瞭：

https://mp.weixin.qq.com/s/0RKuO0Pk7R09wGzgyA43mw

簡單來講最大的差別在於

二分查找樹有可能會左右極度不平衡，造成查找時效率變慢
而紅黑樹有自平衡系統，可以確保樹的深度是平衡的，缺點是增加或是減少節點時會比較耗資源


最近在開發交易所，研究了 Peatio 的交易所撮合引擎，其中有一段就有用到紅黑樹

確切的 code 在這：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L11

所以不禁就想問為什麼這邊要用紅黑樹呢？

原因就是因為在這個演算法中我們是根據 order 的 price 來當排序，假設交易所的 orders 中我們第一個 laoding 進來的 order 是最便宜的或是最貴的，那麼用 binary tree 就會變成左右極不平衡的情況，造成搜尋效率低落，相對的如果用紅黑樹就可以讓整個樹長成左右平衡的大樹，這樣搜尋效率就比較高。

其實 base on 演算法的實作，在 peatio 的演算法中是把 orders 一次 load 進 memory 裡面，所以只有在第一次 loading orders 的時候會花很多資源在紅黑樹自平衡，但一但 loading 完之後大部分的時候都會是在查找 order 而不是新增刪除 order，所以這樣的設計是比較合理的。

查找 order 的部分：https://github.com/peatio/peatio/blob/master/app/models/matching/order_book.rb#L44