替罪羊树

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,替罪羊树,2,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,替罪羊树,替罪羊树的插入,替罪羊树的查找,替罪羊树的删除,3,引入替罪羊树的目的,相比普通的二叉树，那些具有平衡功能的二叉树的节点要,花费更多的内存开销,，如,AVL,树,存储,平衡因子,，,红黑树,存储,颜色,。,替罪羊树（除根节点外）,无需存储额外,的信息，相比别的平衡树,减少,了,内存开销，,并且时间复杂度相同。,4,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,替罪羊树的插入,替罪羊树的查找,替罪羊树的删除,替罪羊树,5,对于二叉排序树的,根结点,1,）若满足,h=h,(h,=,log,1/ ,n,),则称它为,高度平衡（,AVL,红黑树）,2,）,若满足,h=h ,+1,，则称它为,宽松,高度平衡,两个概念,=0.55,5,7,3,6,8,9,h,=,log,1/ 0.55,6,=2,h=3,不满足,h=h ,不是一棵,0.55,高度平衡树,满足,h=h +1,是一棵宽松,0.55,高度平衡树,当,n,一定时,值越小，二叉树越稠密，插入效率越低，查询效率越高,值越大，二叉树越稀疏，插入效率越高，查询效率越低,6,5,2,8,0,6,9,7,0.6,0.6,0.6,0.6,0.6,0.6,0.6,n,7,2,4,1,2,1,1,*,n,4.2,1.2,2.4,0.6,1.2,0.6,0.6,n,左,2,1,2,0,0,0,0,n,右,4,0,1,0,1,0,0,平衡,平衡,平衡,平衡,平衡,平衡,平衡,所以它是一棵,0.6,权重平衡排序树,=0.6,5,8,0,2,6,9,7,权重平衡,若二叉树排序树的,每个结点,都满足,n,左,=,*,n,并且,n,右,=,*,n,则称它为,权重平衡,7,权重平衡,若二叉树排序树的,每个结点,都满足,n,左,=,*,n,并且,n,右,=,*,n,则称它为,权重平衡,(AVL),7,5,8,3,6,9,10,0.6,0.6,0.6,0.6,0.6,0.6,0.6,n,7,2,3,1,1,2,1,*,n,4.2,1.2,1.8,0.6,0.6,1.2,0.6,n,左,3,1,0,0,0,0,0,n,右,3,1,2,0,0,1,0,平衡,平衡,不平衡,平衡,平衡,平衡,平衡,不是一棵,0.6,权重平衡二叉树,=0.6,7,6,3,5,10,9,8,8,特殊情况 当二叉树为,0.5,权重平衡时,即,n,左,=0.5,*,n,并且,n,右,=0.5,*,n,则几乎为,完全二叉树,证：,n-n,右,-1=,n,左,0.5n-1,=,n-n,右,-1 = n,左,=,0.5n,则,n,左,0.5n,n,右,0.5n,树,t,几乎为完全二叉树,定理：如果一棵二叉树,权重平衡，那它一定,高度平衡,反之不一定成立,替罪羊树,(scapegoat tree),的定义：,高度平衡,与,重量平衡,的结合,是一种,二叉排序树,根节点,存储了树的结点,总个数,n,和,上次重建后,的结点个数,n,上次,总能保证,宽松的,高度平衡,即,h=h,+1,(,h,=,log,1/ ,n,),=0.55,5,7,3,6,8,9,h,=,log,1/ 0.55,6,=2,h=3,满足,h=h +1,是一棵宽松,0.55,高度平衡树,是一棵替罪羊树,10,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,替罪羊树,替罪羊树的插入,替罪羊树的查找,替罪羊树的删除,11,替罪羊树的插入,1,）当插入新节点后仍保持,的高度平衡,，则和,普通的二叉排序树,的插入方法一致。,h,：,3,H,：,3,8,20,6,29,10,13,22,19,=0.57,插入,5,h,：,3,H,：,3,8,20,6,29,10,13,22,19,5,=0.57,高度平衡,:,h=,h,(h,=log,1/,n),宽松的,高度衡,:,h= h+1,12,2,）当插入新节点后打破了,的高度平衡,，则要寻找,替罪羊,，把以,替罪羊,为,根节点的子树,重建成一个,新的,0.5,权重平衡,（即完全二叉树）的,二叉排序树,如何寻找替罪羊？,沿着新插入节点的双亲向上找，第一个不满足,权重平衡的结点即为替罪羊,。,高度平衡,:,h=,h,(h,=log,1/,n),宽松的,高度衡,:,h= h+1,权重平衡,:,n,左,=,*,n & n,右,=,*,n,替罪羊树的插入,13,22,20,13,0.57,0.57,0.57,n,2,4,6,*,n,1.14,2.28,3.42,n,左,0,1,1,n,右,1,2,4,平衡,平衡,不平衡,h,：,3,H,：,3,替罪羊树的插入,平均：,O(log(n,),=0.57,8,1,20,19,10,22,29,h,：,4,H,：,3,h,：,3,H,：,3,8,20,1,29,10,13,22,19,替罪羊,插入,29,13,高度平衡,:,h=,h,(h,=log,1/,n),宽松的,高度衡,:,h= h+1,权重平衡,:,n,左,=,*,n & n,右,=,*,n,n,上次,=8,14,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,kd,树的查找,kd,树的删除,kd,树的插入,替罪羊树,替罪羊树的插入,替罪羊树的查找,替罪羊树的删除,15,替罪羊树的删除,一般情况下，替罪羊树的删除和,普通的二叉排序树的删除一样,。,不过，当每次删除完成后，若,n,*,n,上次,，则整个树将,重建成,0.5,权重平衡（,即完全二叉树）的二叉排序树。,（,n,上次,为二叉树上次重建后的结点个数）,16,替罪羊树的删除操作,=0.57,h,：,3,H,：,3,5,13,1,19,9,10,16,22,h,：,3,H,：,3,5,16,1,19,9,10,22,删除,13,h,：,3,H,：,3,5,16,1,22,9,10,h,：,3,H,：,2,5,16,1,9,10,h,：,3,H,：,2,5,16,9,10,删除,19,删除,22,删除,1,n,上次,=n,初始,=8,当,n,*,n,上次,=0.57*8=4.56,时重建,宽松的,高度平衡,n=44.56,重建,平均：,O(log(n,),满足,n,*,n,上次,=0.57,h,：,2,H,：,2,10,16,9,5,n,上次,=4,n=4,替罪羊树的删除操作,h,：,3,H,：,2,5,16,9,10,=0.57,无论插入还是删除替罪羊树总能保证宽松的,高度平衡,18,认识几个基本概念,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,替罪羊树,替罪羊树的插入,替罪羊树的查找,替罪羊树的删除,19,替罪羊树的查找,替罪羊树的查找操作和普通的二叉排序树的操作一样,=0.55,5,7,3,6,8,9,最坏情况：,O(log(n,),20,认识几个基本概念,引入替罪羊树的目的,替罪羊树的定义,替罪羊树的基本操作,总结,替罪羊树的插入,替罪羊树的查找,替罪羊树,替罪羊树的删除,21,总结,1.,替罪羊树不同于别的大部分平衡树，它的节点（除根节点）,不用存储额外的信息,（例如颜色，平衡度）。（根节点存储了,整个树的节点个数,n,和,上次重建后的结点个数,n,上次,）,.,从而,节约了存储空间,。,2.,替罪羊树,不用旋转,来达到平衡，操作简单,。,但是替罪羊树需要,重建,。,22,Thanks,