平衡二叉树-树的旋

心中的日月_pyihe · · 78 次点击 · · 开始浏览    

树结构

  1. 树结构是由一个父节点以及若干个子节点,然后子节点又是其他子节点的父节点,由此而形成的一种结构即是树。其中节点的子节点的子节点叫做该节点的孙节点。如下所示:

  1. 二叉树(Binary Tree, BT)

    二叉树是树结构的应用形式之一,二叉树每个节点至多有两个子节点,如上面第三个树结构所示,位于左边的子节点叫做左孩子或者左子节点,位于右边的叫做右孩子或者右子节点。

  2. 二叉搜索(查找)树(Binary Search Tree, BST)

    二叉搜索树是二叉树的应用之一,在一棵二叉搜索树中,父节点的值总是小于(或者大于)左孩子,而右孩子的值总是大于(或者小于)父节点,由此便构成了一棵有序的树结构。如下图所示:

  1. 平衡二叉树(AVL)

    二叉搜索树是一棵有序的树,但是大多数情况下,往二叉搜索树中插入节点时,可能存在的情况是插入的节点始终位于一个分支上,如下图所示:

这样就出现了一种不尽如人意的情况,就是在一棵二叉搜索树中,某一个分支节点很少,而另一个分支上节点却很多,导致在查找、插入、删除等操作上效率很低。

在一棵二叉搜索树中,对于某一个节点,如果该节点左子树和右子树的高度差的绝对值超过了abs(h) > 1,则称该树为非平衡二叉搜索树。为了改善这种情况,便出现了平衡二叉树,顾名思义,平衡二叉树任意一个节点的左子树和右子树高度差的绝对值都abs(h)<=1。平衡二叉树是在二叉搜索树的基础上,增加了平衡二叉树的操作,使得二叉搜索树是一棵平衡树。如下图为一棵平衡二叉树:

平衡查找树的平衡

前面已经提到什么是平衡二叉树,那么怎么样形成一棵平衡的二叉树呢?

权威们给出的答案是旋转,即通过对二叉树进行旋转来改变树的结构并且不改变节点值的顺序,从而得到一棵平衡的二叉树。下面介绍树的旋转,树的旋转分为左旋转、右旋转以及左右旋转,右左旋转。

因为树的节点个数变化为1、2、3...n,所以当节点总数小于3时一棵二叉搜索树一定是平衡的,如下图:

此时左子树的高度与右子树的高度差的绝对值为1,所以是平衡的(在下文中提到的高度差都是左子树高度减去右子树高度)。但是随着节点的插入,有可能变成不平衡的了。以下为需要旋转操作进行平衡二叉树的情况,均是针对最少节点数的情况,即需要旋转操作的最小子树。

注: 下文提到的高度差均为左子树减去右子树的高度差的绝对值,同时本文中的平衡二叉树为左节点小于父节点,父节点小于右节点

  1. 左旋转
  • 在右子树添加节点造成不平衡。root只有右孩子的情况,以root的右孩子为中心,向左(逆时针)旋转root节点,旋转结果为root节点变为root右孩子的左孩子,如下图, 在右子树添加节点(图中的16),造成不平衡:
  • 在右子树添加节点造成不平衡,其中root同时有左右子树,左子树只有一个节点,右孩子只有一个右子节点,添加一个节点(下图中的17)后造成不平衡树,此时可以看到,root的右子树不平衡,此时按照第一种旋转方式可以将右子树旋转平衡,进而使整棵树平衡,如下图:
  • 在右子树添加节点造成不平衡,其中root只有一个左孩子,root的右孩子同时存在左右孩子,如下图:

从上面可以看出,如果root右子树比左子树高2,并且右子树的右子树比右子树的左子树高,则执行左旋转,以下是左旋转的代码(Golang):

   type AVLNode struct {
        Data   Element  //存放的元素
        Height int      //存放节点的高度
        Left   *AVLNode //左子树
        Right  *AVLNode //右子树
   }
    
   func (avl *AVLNode) Max() *AVLNode {
    node := avl
    for node.Right != nil {
        node = node.Right
    }
    return node
   }
   
   func getHeight(avl *AVLNode) int {
    if avl != nil {
        return avl.Height
    }
    return 0
   }
   
   func max(h1, h2 int) int {
    if h1 > h2 {
        return h1
    }
    return h2
   }
   
   func leftRotate(avl *AVLNode) *AVLNode {
       if avl == nil {
           return nil
       }
        node := avl.Right
        avl.Right = node.Left
        node.Left = avl
    
        avl.Height = max(getHeight(avl.Left), getHeight(avl.Right)) + 1
        node.Height = max(getHeight(node.Left), getHeight(node.Right)) + 1
        return node
   }
  1. 右旋转
  • 在左子树添加节点造成不平衡, root没有右孩子,同时左孩子只有左孩子一个节点, 此时以root的左孩子为中心,进行右旋转(顺时针旋转), 将root左孩子提升为root,root降为左孩子的右孩子,如下图:
  • 在左子树添加节点造成不平衡, root同时包含左右孩子,右孩子没有子节点,左孩子只有一个左孩子节点,此时root的左子树为不平衡树,按照上面的方式对左子树进行右旋转得到平衡树,如下图:
  • 在左子树添加节点造成不平衡, root只有一个右孩子, 左孩子同时有左右孩子, 在左孩子的左孩子下添加一个节点, 如下图:

从上面可以看出, 如果root左子树比右子树高2,并且左子树的左子树比左子树的右子树高,则执行右旋转,以下是右旋转的代码(Golang):

    func rightRotate(avl *AVLNode) *AVLNode {
       if avl == nil {
           return nil
       }        
       node := avl.Left      //左子树
       avl.Left = node.Right //左子树的右子树变为左子树
       node.Right = avl      //avl降为左子树的右子树
    
        //更新节点高度
        avl.Height = max(getHeight(avl.Left), getHeight(avl.Right)) + 1
        node.Height = max(getHeight(node.Left), getHeight(node.Right)) + 1
        return node
    }
  1. 左右旋转

左右旋转是指先执行左旋转再执行右旋转。

  • 在左子树添加节点造成不平衡,root只有左子树,且左子树只有一个节点,如下图:
  • 在左子树添加节点造成不平衡,root同时有左右孩子,root的左孩子同时有左右孩子,在root的左孩子的右孩子上添加左节点造成不平衡,如下图:
  • 在左子树添加节点造成不平衡,root同时有左右孩子,root的左孩子同时有左右孩子,在root的左孩子的左孩子上添加右节点造成不平衡,如下图:

从上面可以看出, 如果root左子树比右子树高2,并且左子树的右子树比左子树的左子树高2,则先执行左旋转,再执行右旋转,以下是左右旋转的代码(Golang):

    //先将左孩子左旋转,自己再右旋转
    func (avl *AVLNode) leftRightRotate() *AVLNode {
        avl.Left = avl.Left.leftRotate()
        return avl.rightRotate()
    }
  1. 右左旋转

右左旋转是指先执行右旋转再执行左旋转。

  • 在右子树添加节点造成不平衡, root只有右子树,且右子树只有一个节点,如下图:
  • 在右子树添加节点造成不平衡, root同时有左右孩子,root的右孩子同时有左右孩子,在root的右孩子的左孩子上添加右节点,如下图:
  • 在右子树添加节点造成不平衡, root同时有左右孩子,root的右孩子同时有左右孩子,在root的右孩子的左孩子上添加左节点,如下图:

从上面可以看出, 如果root右子树比左子树高2, 并且右子树的右子树比右子树的左子树矮, 则执行右旋转后再执行左旋转,以下是左右旋转的代码(Golang):

    //先将右孩子右旋转,然后自己右旋转
    func (avl *AVLNode) rightLeftRotate() *AVLNode {
        avl.Right = avl.Right.rightRotate()
        return avl.leftRotate()
    }

综上可以得出平衡二叉查找树的函数为:

//调整树为二叉平衡树
func balance(avl *AVLNode) *AVLNode {
    if avl == nil {
        return nil
    }
    if getHeight(avl.Right)-getHeight(avl.Left) == 2 {
        if getHeight(avl.Right.Right) > getHeight(avl.Right.Left) {
            avl = avl.leftRotate()
        } else {
            avl = avl.rightLeftRotate()
        }
    } else if getHeight(avl.Left)-getHeight(avl.Right) == 2 {
        if getHeight(avl.Left.Left) > getHeight(avl.Left.Right) {
            avl = avl.rightRotate()
        } else {
            avl = avl.leftRightRotate()
        }
    }
    return avl
}

插入、删除节点

以上为树的旋转操作,用于平衡二叉查找,对于二叉查找树,每添加或者插入一个节点后均需要执行一次平衡操作。代码如下:

//添加节点
func (avl *AVLNode) AddNode(data Element) (root *AVLNode, ok bool) {
    defer func() {
        if ok {
            root = balance(avl)
            root.Height = max(getHeight(root.Left), getHeight(root.Right)) + 1
        }
    }()
    
    var target = &AVLNode{
        Data:   data,
        Height: 1,
        Left:   nil,
        Right:  nil,
    }
    
    cmpResult := avl.Data.Compare(data)
    switch {
    case cmpResult > 0:
        if avl.Left == nil {
            avl.Left = target
            ok = true
            return
        }
        avl.Left, ok = avl.Left.AddNode(data)
        return
    case cmpResult < 0:
        if avl.Right == nil {
            avl.Right = target
            ok = true
            return
        }
        avl.Right, ok = avl.Right.AddNode(data)
        return
    default:
        ok = true
        return
    }
}

func (avl *AVLNode) RemoveNode(data Element) (root *AVLNode, ok bool) {
    defer func() {
        if ok && root != nil {
            root = balance(root)
            root.Height = max(getHeight(root.Left), getHeight(root.Right)) + 1
        }
    }()
    
    var temp *AVLNode
    cmpResult := avl.Data.Compare(data)
    switch {
    case cmpResult > 0:
        if avl.Left == nil {
            return nil, false
        }
        temp, ok = avl.Left.RemoveNode(data)
        if ok {
            avl.Left = temp
        }
        root = avl
        return
    case cmpResult < 0:
        if avl.Right == nil {
            return nil, false
        }
        temp, ok = avl.Right.RemoveNode(data)
        if ok {
            avl.Right = temp
        }
        root = avl
        return
    default:
        if avl.Left == nil && avl.Right == nil {
            return nil, true
        }
        if avl.Left == nil {
            root, ok = avl.Right, true
            return
        }
        if avl.Right == nil {
            root, ok = avl.Left, true
            return
        }
        //将左子树最大节点提升到头节点,并将该最大节点从左子树中删除
        avl.Data = avl.Left.Max().Data
        avl.Left, ok = avl.Left.RemoveNode(avl.Data)
        root = avl
        return
    }
}

最后

原文链接

源码跳转

谢谢!


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:心中的日月_pyihe

查看原文:平衡二叉树-树的旋

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

78 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传