Please enable JavaScript.

Coggle requires JavaScript to display documents.

Data Structure (:moneybag:Tree (:three:Red-Black Tree (:moneybag:Property,…

- - - - :key:层1期待值n, 层2期待值n/2, 层3期待值n/4...
      - :moneybag:2n
    - - :moneybag:查找
        
        :moneybag:O(logn)
        
        :bulb:图文形式
        
        skiplist介绍
      - :moneybag:删除
        
        :moneybag:O(logn)
      - :moneybag:插入
        
        :moneybag:O(logn)
    - - :key:最高层期待值为1个数据项
      - :moneybag:log2(n)
    - - :explode:对于事件A，如果它发生的概率至少为1-cα/nα，其中cα仅取决于α，那么我们称它为高概率。
      - Skip List（跳表）分析
- - - - :two:删除
        
        :snowflake:把要删的转到叶节点就ok了
        
        :fast_forward:AVL树
      - :one:插入
        
        :moneybag:旋转
        
        :explode::one:4种情况:左左,右右,左右,右左 :two:左左和右右单旋转(祖父转),左右和右左双旋转
    - - :explode:左子树高度-右子树高度
      - :star:取值为-1,0,1
  - - - :one:Splaying
        
        :moneybag:旋转
        
        :two:我有一个父亲
        
        :one:我的父亲是root
        
        :explode:单次旋转:check:
        
        :two:我的父亲p还有一个父亲,记作g
        
        :one:我,p,g构成了左左或右右
        
        :explode:祖父,父亲都转一次,共转两次.左左=>右右,右右=>左左:check:
        
        :two:我,p,g构成了左右或右左
        
        :explode:双旋转,先父亲,后祖父:check:
        
        :one:我(node)已经是root了:check:
  - - - :one:或红或黑
      - :two:红色的上下都黑
      - :three:每个节点到NULL的所有路径黑节点都相同
      - :four:根是黑的
    - - :one:Insert
        
        :one:插入的时候按照BST插入,默认red
        
        :one:没有父亲
        
        :two:我有父亲
        
        :one:我父亲是黑的:check:
        
        :two:我父亲是红的
        
        :one:我叔叔是黑的
        
        :one:我是右孩子
        
        1 more item...
        
        :two:我是左孩子
        
        1 more item...
        
        :two:我叔叔是红的
        
        :explode:父亲和叔叔变黑,祖父变红,不再检查我,而是开始检查祖父位置
        
        :moneybag:口诀
        
        :one:父红叔黑左,父黑祖红右
        
        :two:都红就变黑,祖父很开心,有事找他
        
        :moneybag::fast_forward:case图解
    - - :explode:内节点有几个孩子.如degree=1表示只有一个孩子
      - :star:红黑树里只有一个孩子的节点,这个节点的孩子肯定是害羞(红)得单身(没有孩子)的
- - - - :explode:从一个节点到最近的null的长度
      - :star:Npl(NULL)=-1.Npl(一个孩子为NULL的节点)=0
    - - :one:merge
        
        :explode:我们称root内容大的为大树,小的为小树.则每次都是大树和小树的右边一起合并,合并后放在小树右边,然后看要不要交换
        
        :warning:大树包括root,小树不用root
  - - - :one:merge
        
        :explode:大树和小树的右边合并,合并后放在小树右边,然后一定交换
  - - - :two:delete-min
        
        :moneybag:复杂度
        
        :explode:O(logN)
        
        :snowflake:找到最小值,然后合并两个二项队列
      - :one:merge
        
        :moneybag:复杂度
        
        :explode:O(logN)
    - - :explode:The rank of a node=the number of children
      - :tornado:rank(B0)=0,rank(B1)=1,...,rank(Bk)=k
- - - - :explode:检索到的有多少是相关(正确)的
    - - :explode:相关的里面我recall(提取)了多少