Day.29 其他树的介绍

树有非常多变型，下面是Wiki的截图

以下简单介绍几种常听到的～

AVL Trees、Red Black Trees

前几篇介绍的是最基本的二元树，但实际上不太会直接用到二元树，因为它不会做平衡，如果一直对它做insert，很容易就会歪一边，大大影响效能。之前有提到的两种比较常听到的平衡树，AVL Trees 和 Red Black Trees。
平衡树在做insert的时候，会做旋转操作(左旋，右旋等)，根据值去调动节点的位置，让整个树一直保持在平衡的状态。
一般来说Red Black Trees在insert&delete上比AVL树有优势，AVL树则在serach有优势。

两种树的程序都很复杂，因为在插入跟删除的时候，都有很多case要处理，大家有兴趣可以再去研究
不过一般来说，我们有需要都会去github找package来用XD，很少情境要你去刻一个出来

B+ Tree

这一种就是MySQL InnoDB底层的资料结构
平衡二元树在搜寻的速度上的确很优秀，但不好去读取大量的资料，如果我们要去找id 1到20的资料，那就要搜寻20次。其次二元树每一个节点底下只可以有两个子节点，DB资料随便都几百万千万，这颗树的深度就很可怕了，这也会影响到搜寻的速度。

而B+ Tree就解决了这些问题
最下面绿色的是真正的资料，以MySQL来说是一页，页跟页之间有做链结，每一页都有下一页的地址。以B+Tree来搜寻id 1到20的资料，我们就可以透过树来找到id 1的页在那，再从页里面照顺序找1~20的资料，就可以一次回传！树就是一个索引的概念，让我们可以快速找到页的位置～

图源在这一篇文章找的，内文写得很细，大家有兴趣可以看看～

Binary Heap

中文叫二元堆积，是为了解决Priority Queue的一种方式
那什麽是Priority Queue？
简单来说在队列里面加入权重，举个例假如一堆平民先进去排队，但权贵人土可以随时插队的概念(像打疫苗)，又或者是待办清单，原本就照重要的程度去做排序，但突然有一个紧急的事情，就会插到清单最前面。

Min Heap (root为最小值)

            1         
         /      \        
       2         3                      
    /    \     /   \                 
   4      5   6     7               
  / \    / \                      
 8  9   10 11                     

Max Heap (root为最大值)

          11 
       /      \ 
     9         10
   /   \     /    \ 
  5      6   7      8
 / \    / \
1   2  3   4 

再做Heap sort就可以做出Priority Queue的效果，大家有兴趣再去研究～

今天先到这样～Bye