Splay Tree and AVL Tree

Splay Tree

一套规则，用于提高BST的读效率，当node s 被读到，就进行splay，也就是说读得多的靠近根

• single rotation
  
• double rotation
  • zigzag
    
  • zigzig
    

AVL Tree(Adelson-Velskii-Landis):平衡树

• balance factor BF(node) = 左孩子高度-右孩子高度=-1,0,1
• rotation：就是看长出来的树是右孩子的右孩子就是RR，依次类推，
  • RR rotation
    
  • LL rotation
    
  • LR rotation
    
  • RL rotation