国家集训队2007论文集 陈启峰

《国家集训队2007论文集 陈启峰》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、SizeBalancedTree中山纪念中学高二陈启峰344368722@QQ.com总揽全文BST&Rotations:预备知识SizeBalancedTree:定义&功能介绍Maintain:核心操作Analysis:时间复杂度分析Advantage:七大优点探索历程:感性与理性中螺旋前进BinarySearchTreeBinarySearchTree(abbr.BST)是一棵具有以下性质的二叉树：对于BST中任意一个结点，(1)左子树中的关键字不大于它的关键字;(2)右子树中的关键字不小于它的关键字.BinarySearchTree为了方便讨论我们定义：Left[T]:结

2、点T的左儿子Right[T]:结点T的右儿子S[T]:以T为根的子树的结点个数（大小）Rotations为了保持BST平衡，我们通常使用Rotations来改变树的形态。Rotations分为相对的两种类型：Right-RotateLeft-RotateRight-RotateTLABRotations表示结点表示BSTRRight-RotateTLABRotationsRTLABRotationsRight-RotateRRight-RotateTLABRotationsRSizeBalancedTreeSizeBalancedTree(abbr.SBT)是一种通过大小来保持

3、平衡的BST。它总是满足：对于SBT的每一个结点t,性质(a)s[right[t]]≥s[left[left[t]]],s[right[left[t]]]性质(b)s[left[t]]≥s[right[right[t]]],s[left[right[t]]]i.e.每棵子树的大小不小于其兄弟的子树大小SizeBalancedTrees[R]≥s[A],s[B]s[L]≥s[C],s[D]TLRABDCSizeBalancedTreeInsert插入Delete删除Find查找Rank排名Select找第K小Pred前趋Succ后继当我们插入或删除一个结点后，ＳＢＴ的大小就发生了

4、改变。这种改变有可能导致性质(a)或(b)被破坏。这时，我们需要修复这棵树。MaintainMaintainＭaintain(T)用于修复以T为根的SBT。调用Maintain(T)的前提条件是T的子树都已经是SBT了Maintain由于性质(a)和(b)是对称的，下面仅对性质(a)被破坏的情况进行分析：MaintainCase1:s[Left[Left[T]]>s[Right[T]]S[A]>S[R]TLRABDCMaintainCase1:s[Left[Left[T]]>s[Right[T]]Right-Rotate(T)TLRABDCMaintainCase1:s[Lef

5、t[Left[T]]>s[Right[T]]Right-Rotate(T)TLRABDCMaintainCase1:s[Left[Left[T]]>s[Right[T]]Right-Rotate(T)TLRABDCMaintainCase1:s[Left[Left[T]]>s[Right[T]]Right-Rotate(T)TLRABDCMaintainCase1:s[Left[Left[T]]>s[Right[T]]Right-Rotate(T)Maintain(T)TLRABDCSBTMaintainCase1:s[Left[Left[T]]>s[Right[T]]Righ

6、t-Rotate(T)Maintain(T)Maintain(L)LASBTSBTMaintainCase2:s[right[left[t]]>s[right[t]]s[B]>s[R]TLRADCBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)TLRADCBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)TLRADCBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)TLRAD

7、CBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)TLRADCBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)Right-Rotate(T)TLRADCBEFMaintainCase2:s[right[left[t]]>s[right[t]]Left-Rotate(L)Right-Rotate(T)TLRADCBEFMaintainCase2:s[rig