代码之家  ›  专栏  ›  技术社区  ›  Konrad

平衡AVL树

  •  1
  • Konrad  · 技术社区  · 7 年前

    这是树: enter image description here

    然后我必须在这个AVL树中插入65。这会导致不平衡,根据我的理解,需要左右旋转。

    http://robinsswei.github.io/VisGraphs/avltree.html : enter image description here

    以下是我的教科书中给出的正确答案:

    enter image description here

    哪一个是正确的答案?

    3 回复  |  直到 7 年前
        1
  •  1
  •   Conniption    7 年前

    AVL Tree Diagram

    嘿,好了,

    AVL树要求每个节点左右子节点的高度最多相差+1或-1。(-1,0,1)

    例如,在第一个图中,在插入之前,Id从下到上。节点87没有任何子节点,这将是0。节点45只有一个子节点,因此我们计算87的0高度。节点3没有子节点,因此这也将是0。节点34有两个子节点,3和45。它们之间的差异只有1。所有节点都通过了AVL树测试。


    执行简单的左旋转,满足AVL属性。

        2
  •  0
  •   Jaimin    7 年前

    根为45的第二个是正确答案。平衡AVL树的两个子长度(深度)必须相同。因此,进入65岁后,你的树将不平衡。所以你们需要把节点移到左边。

        3
  •  0
  •   KID0031    5 年前