平衡搜索树的左单旋、右单旋、咗右双旋、右左双旋
在平衡搜索树中进行插入结点时有可能会破坏整棵树的平衡。为了保证平衡不被破坏就要对一些节点进行旋转,從而来降低树的高度这样也能保证树的平衡。
(上图中的▲结点有可能是NULL也有可能不为空。。下同)
从图中可以看出进行左单旋時,只是改变了parent的右指针以及subR的左指针指向将subR的左子树(subRL)作为parent的右子树,并让parent作为subR的左子树很明显,这样做就降低了这棵树的高度
进行旋转时需要注意的两点:
2.parent是否为根节点?如果parent为根节点那么旋转完成后只需将subR赋给根节点即可;但如果parent不为根节点,即parent是某一节點ppNode的子树就要判断parent在ppNode的左还是右,这样才能确定subR的位置
//判断subR应链接在ppNode的左子树还是右子树同左单旋一样,右单旋转是将subL的右子树结点賦给parent的左指针并让parent自己作为subL的右子树。
//如果parent不为根节点判断其在上一个结点的右还是左了解了单旋之后,双旋就比较简单只是进行叻两步单旋而已