平衡二叉树的旋转
平衡二叉树的旋转
分为:左旋和右旋。
触发时机:当添加一个节点之后,该树不再是一颗平衡二叉树。
graph TD subgraph 2 ["平衡二叉树"] 10--> 7 --> 4 10 --> 11 --> 12 end subgraph 1 ["不平衡二叉树"] A((7)) --> B((4)); A --> C((10)) --> D((11)) --> E((12)); end
左旋:就是将根节点的右侧往左拉,原先的右子节点变成新的父节点,并把多余的左子节点出让,给已经降级的根节点当右子节点。
右旋:就是将根节点的左侧往右拉,原先的左子节点变成新的父节点,并把多余的右子节点出让,给已经降级的根节点当左子节点。
平衡二叉树-左左:
左左:当根节点的左子树的左子树有节点插入,导致二叉树不平衡
flowchart TD subgraph 1 A1((7))-->A2((4)) & A3((10)) A2((4))-->A4((2))-->A6((1)) A2((4))-->A5((5)) end subgraph 2 a2((4))-->a4((2))-->a6((1)) a2((4))-->a1((7))-->a3((5)) a1((7))-->a5((10)) end
平衡二叉树-左右:
左右:当根节点左子树的右子树有节点插入,导致二叉树不平衡。先将左子树左旋,然后再右旋
flowchart TD subgraph 1 A1((7))-->A2((4)) & A3((10)) A2((4))-->A4((2)) A2((4))-->A5((5))-->A6((6)) end subgraph 2 a1((7))-->a5((5))-->a2((4))-->a4((2)) a1((7))-->a3((10)) a5((5))-->a6((6)) end subgraph 3 c5((5))-->c2((4))-->c4((2)) c5((5))-->c1((7)) c1((7))-->c6((6)) c1((7))-->c3((10)) end
平衡二叉树--右右:
右右:当根节点右子树的右子树有节点插入,导致二叉树不平衡
平衡二叉树-右左:
右左:当根节点右子树的左子树有节点插入,导致二叉树不平衡