Chinaunix首页 | 论坛 | 博客
  • 博客访问: 1016482
  • 博文数量: 128
  • 博客积分: 10012
  • 博客等级: 上将
  • 技术积分: 2050
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-15 17:49
文章分类

全部博文(128)

文章存档

2011年(16)

2009年(57)

2008年(55)

分类:

2009-10-12 00:50:53

heap树的每一个父节点的都比它的两个子节点要大或者要小,父节点比子节点大的称之为大堆树,反之父节点比子节点小的称之为小堆树。
举例子构造一个heap树就什么都明白了,以大堆树为例
用这样(24,49,13,20,59,23,90,35)的一组数据来构造一个大堆树
如何构造呢
1. 24根节点                                        
                 24
2. 49,挂在24左子节点,但49比24大,交换           
              49        49                              
              / \
             24                             
3. 13,挂在49的右子节点,同时13又比49小,不交换                   
                49
               /  \
              24  13
4. 20,挂在24左子节点,同时20又比24小,不交换                    
                49                                             
               /  \
             24   13
             /
            20
5. 59,挂在24的右子节点,59比24大,交换,59比49大,交换           
                 59
                /  \
               49   13
              / \
             20  24
6. 23,挂在13的左子节点,23比13大,交换,23比59小,不交换                
                  59
                 /  \
                49   23
               / \   / \
              20 24 13
7. 90,挂在23的右子节点,但90比23大,交换,90比59大,交换                   
                  90
                 /  \
                49   59
               / \   / \
              20 24 13 23
8. 35,挂在20左子节点,但35比20大,交换,35比49小,不交换                    
                   90
                  /  \
                 49   23
                /  \  /  \
              35  24  13  23
              /
             20
AVL树,自平衡二叉查找树,它的每一个父节点的左子树都比父节点要小,右子树都比父节点要大。这里涉及到一个左旋和右旋的问题,先来讲讲什么是左旋,什么是右旋。以下面树为例,下面的书是一个最小不平衡二叉树,我们看到b1子节点到a节点的深度为3,a1到a的深度为1,两者深度差了2,所以称为不平衡。我们看看右旋后得到的树
            a                                            c
           / \                                          /  \
          c   a1           右旋                        b    a
         / \                                          /    / \ 
        b  c1                                        b1   c1   a1
       /
      b1  
我们来总结下右旋的法则:将c的父节点和右子节点断开,将a作为c的右子节点,c1为a的左子节点
同理,我们看下左旋
       a                                              c
      / \                                           /   \
    a1   c                                         a     c1
        / \                                       / \      \
       b   c1             左旋                   a1  b      b1
            \
             b1
 
最小不平衡2叉树发生自旋的四种情况:
单向右旋平衡处理RR:由于在*a的左子树根结点的左子树上插入结点,*a的平衡因子由1增至2,致使以*a为根的子树失去平衡,则需进行一次右旋转操作;
单向左旋平衡处理LL:由于在*a的右子树根结点的右子树上插入结点,*a的平衡因子由-1变为-2,致使以*a为根的子树失去平衡,则需进行一次左旋转操作;
双向旋转(先左后右)平衡处理LR:由于在*a的左子树根结点的右子树上插入结点,*a的平衡因子由1增至2,致使以*a为根的子树失去平衡,则需进行两次旋转(先左旋后右旋)操作。
双向旋转(先右后左)平衡处理RL:由于在*a的右子树根结点的左子树上插入结点,*a的平衡因子由-1变为-2,致使以*a为根的子树失去平衡,则需进行两次旋转(先右旋后左旋)操作。
 
最后举个例子什么都明白了,还是用(24,49,13,20,59,23,90,35),我们来构造一个AVL树,来看看结果
             24
            /  \
           20    59
          / \    / \
         13  23 49  90
                /
                35
阅读(2357) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~