search

bosthhe1 / cpushpush

0 stars 0 forks source link

平衡搜索二叉树旋转图 #31

Open bosthhe1 opened 1 year ago

bosthhe1 commented 1 year ago

图中的p代表parent，g代表grandparent，s代表sub,n代表新插入节点newNode

bosthhe1 commented 1 year ago

右旋 我们以右旋为例子，我们在不破坏平衡搜索二叉树的规则下，将树的高度降低 将sub->right给parent->left,然后将链接关系改一下就可以达到目的，需要注意的是，需要调节平衡因子，这里涉及到的节点都调为0 image

bosthhe1 commented 1 year ago

左旋 image

bosthhe1 commented 1 year ago

双旋转会较为麻烦一点，但是理解之后也很简单

bosthhe1 commented 1 year ago

双旋就是将sr的左给左边，右给右边，自己当grandparent，最后需要将平衡因子调整一下就可以了 情况1 g为1，其他都为0 image

这里就是s为-1，其他都是0 情况2 image

bosthhe1 commented 1 year ago

右边的双旋参照左边，注意平衡因子的调节即可