首页 > 试题广场 >

AVL树是平衡二叉查找树，在AVL树中任何节点的两个子树的高

[单选题]
AVL树是平衡二叉查找树，在AVL树中任何节点的两个子树的高度最大差别为1，现有一结点序列（100，70，50，80，90，60），逐个插入一颗空的AVL树，插入过程中，树不断调整，则在上述情境下，分析正确的是（  ） 
  • 树中插入90时，破坏平衡了，需要进行RL调整
  • 树中插入90时，破坏平衡了，需要将90变为100和80的父节点
  • 树中插入50时，破坏平衡了，需要将50变为70的父节点
  • 树中插入80时，破坏平衡了，需要将80变为100的父节点
  • 树中插入90时，破坏平衡了，需要将80变为根节点，90和100变为80的右孩子
查看正确选项
添加回答
杂货店的阿猿头像 杂货店的阿猿
发表于 2022-02-26 22:37:20 回复(2)
求职不易呀头像 求职不易呀
        70
     /        \
50            90
  \            /    \
   60    80    100
发表于 2023-04-18 16:09:50 回复(0)
牛马找工作ing头像 牛马找工作ing
90的发现者的在最低点祖先节点，100的左子树的右边，故是LR调整，先右单旋，再左单旋，
原来为:
                    100
                  /
                80
                      \
                        90
失衡最小祖先为100，故先80(100的子树)右旋调整，变为 
        100
        /
    90
    /
80
失衡最小祖先为100，故先90(100的子树)左左旋为
         90
        /    \
      80     100
发表于 2021-08-13 16:26:14 回复(1)
提交观点

问题信息

C++工程师 PHP工程师 百度 2021 Java工程师
上传者：小小
难度：
3条回答 1313浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号