首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python 学习手册
Python Cookbook
Python 基础教程
Python Sites
PyPI - Python Package Index
http://www.simple-is-better.com/
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
宝塔
V2EX  ›  Python

一个 AVL 树的问题

  •  
  •   androidzhujiao · 277 天前 · 812 次点击
    这是一个创建于 277 天前的主题,其中的信息可能已经有所发展或是发生改变。
    比如 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
    
    但是逻辑上不太清楚(或者说先处理哪个故障点呢)
    
        1
    noli   277 天前 via iPhone
    avl 树中有 10 9 6 三个节点上时候,就不可能是你现在画出来的样子吧?
        2
    ileadall   277 天前
    楼上加一,但事实上是下向上调整高度的时候,第一个不平衡的点来决定哪一种旋转类型。
        3
    drizztdouu00   277 天前 via Android
    每次插入后 会调整高度 不会出现你说的这种情况
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2158 人在线   最高记录 5043   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 25ms · UTC 03:07 · PVG 11:07 · LAX 19:07 · JFK 22:07
    ♥ Do have faith in what you're doing.