二叉排序树
这是所有树最基础的操作,分为左旋转和右旋转,下图直接取自算法导论
可以看到右旋操作时,y的右子树一直保持不变,左旋操作时,x的左子树一起保持不变
旋转是很多二叉平衡树维持平衡的主要手段,在这里复习一下。其实旋转过程中节点位置的变化只要遵循一个原则就行了:比Root小的在左子树,比Root大的在右子树。(当然这里前提条件是左小右大)。
情况一:插入F节点导致失衡:
这里失衡的是A的左右子树,很容易就可以想到旋转B-A链,值得注意的是E节点,它原先在B的右子树,现在也依然在B的右子树,它原先在A的左子树,现在也依然在A的左子树。
若插入F节点在D的右子树处,旋转操作依然是上图那样,不谈。
但如果插入F节点是E的孩子就不一样了。
情况二:插入F节点导致失衡:
插入节点是E的孩子时,如果我们还像上面那样旋转B-A链,旋转后的树依然是不平衡的。事实上,这样的旋转使得B成为了新的根节点,而原图中比B大的节点有4个,比B小的节点只有D,若B为根其左子树只能为D,必定是不平衡的。
我们仔细观察原图,这里E节点是很特殊的节点。首先它是实际执行了插入操作的节点,其次图中比E小的节点有B、D、F,比E大的节点有A、C。如果能够让E节点做新的根节点就很好平衡了,那么怎样让E节点“上位”呢?
方法是进行两次旋转,如下图:
E节点恐成最大赢家……
插入节点是E的右子树的情况与之类似,这里给出旋转图:
F比E大,双旋之后还是在E的右节点。
双旋看图理解起来简单,实际实现时要注意,我们可以判断失衡的是A节点,由A有直接关系的是B和C,那么我们怎么知道新插入的F节点是D的子树还是E的子树呢?这里的方法是比较F节点值与B的大小,大则是E的子树,要左-右共两次旋转,小则是D的子树,要一次右旋转。
当然还要考虑镜像情况:
情况三:插入 F导致失衡:
进行一次左旋,关注D节点,它比C小,旋转后依然在C的左子树。
情况四:插入F导致失衡:
这时候左旋失败,理由和之前右旋失败类似,比C节点大的节点只有一个E,C是没法做新的根节点的。这里特殊的是D节点。
进行右-左两次双旋就可以了。D节点:爽到……
插入节点是D的右子树情况类似,RT:
情况一对应教科书上的 LL 类型。 情况二队应教科书上的 LR 类型。 情况三对应教科书上的 RR 类型。 情况四对应教科书上的 RL 类型。