V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
androidzhujiao
V2EX  ›  Python

一个 AVL 树的问题

  •  
  •   androidzhujiao · 2019-02-12 14:55:48 +08:00 · 1825 次点击
    这是一个创建于 2095 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如 10 9 这俩数  插入一个 6
         10
          /
        9
       /
      6
    
    这种旋转完之后就是
        9
        / \
       6. 10
    
    
    但如果是这种的话
    
    
    10 9 6 插入一个 4
                    10
    	       /
    	     9
    	    /
               6
              /
            4
    
    10 和 9 都可以认为这棵树不平衡,也就是说 10 和 9 的左右子树都不平衡(或者说是故障点,等于现在树里有 2 个故障点)
    
    逻辑上该认为哪个是轴呢
    
    代码该从哪个节点开始处理呢
    
    我知道旋转之后的结果肯定是这
              9
             /  \
           6.   10
          /
         4
    
    但是逻辑上不太清楚(或者说先处理哪个故障点呢)
    
    noli
        1
    noli  
       2019-02-12 17:14:00 +08:00 via iPhone
    avl 树中有 10 9 6 三个节点上时候,就不可能是你现在画出来的样子吧?
    ileadall
        2
    ileadall  
       2019-02-12 21:02:44 +08:00
    楼上加一,但事实上是下向上调整高度的时候,第一个不平衡的点来决定哪一种旋转类型。
    drizztdouu00
        3
    drizztdouu00  
       2019-02-13 09:56:32 +08:00 via Android
    每次插入后 会调整高度 不会出现你说的这种情况
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   995 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:38 · PVG 05:38 · LAX 13:38 · JFK 16:38
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.