精华内容
下载资源
问答
  • 平衡二叉树删除

    2021-02-18 17:35:22
  • 平衡二叉树的实现我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:❝ 年轻人你不要过度消费我,这好吗?这不好。 ❞所以我们针对这...

    7accb65d2ede943318702ca4f2ec0bd8.png

    平衡二叉树的实现

    我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:

    ❝ 年轻人你不要过度消费我,这好吗?这不好。

    所以我们针对这个问题进行优化,就出现了「平衡二叉树」

    何为平衡,平衡是指,二叉树中任意节点的左右子树的高度差都不大于1。当插入或删除一个节点时,我们需要通过一次或多次树的「旋转」来保持二叉树的平衡。

    树的旋转分为「左旋」「右旋」两种具体操作,这两种操作是完全相反的,互为逆操作。

    左旋是「将该节点的右子树逆时针旋转」,右旋是「将该节点的左子树顺时针旋转」

    对于一个节点node进行左旋操作时,具体操作为:「将node.right子树取下,node.right节点称为新的根节点newRoot,将node接在newRoot的左节点,newRoot.left取下接在node的右节点上。」

    右旋操作相反:「将node.left子树取下,node.left节点作为新的根节点newRoot,将node接在newRoot的右节点,newRoot.right取下接在node的左节点上。」

    982142556e0f777ee1b5e30d253d54ee.png

    AVL插入节点有四种情况,分别为「左子树左节点,左子树右节点,右子树左节点,右子树右节点」

    b71f4bf6c33b2980090367aa1605758b.png

    对于左子树左节点,进行一次右旋操作,右子树右节点,进行一次左旋操作可以恢复平衡。

    对于左子树右节点和右子树左节点需要两次旋转才能恢复平衡。

    代码实现:

    // 构造节点,使用节点的height属性判断是否平衡
    class Node {
      constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.height = 1
      }
    }
    
    class AVL {
      constructor() {
        this.root = null
      }
      
      // 获取节点的高度
      getHeight(node) {
        if(!node) return 0
        return node.height
      }
      
      // 左旋的具体操作,将node节点的node.right取下,作为新的根节点,node.right.left取下
      // 将node接在node.right节点的左节点,node.right.left节点接在node的右节点
      leftRotate(node) {
        let newRoot = node.right
        let newNode = newRoot.left
        newRoot.left = node
        node.right = newNode
        node.height = 1 + Math.max(this.getHeight(node.left), 
                                   this.getHeight(node.right))
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left), 
                                      this.getHeight(newRoot.right))
        return newRoot
      }
      
      // 右旋的操作与左旋相反,将上述代码中的left换成right,right换成left就行
      rightRotate(node) {
        let newRoot = node.left
        let newNode = newRoot.right
        newRoot.right = node
        node.left = newNode
        node.height = 1 + Math.max(this.getHeight(node.left),
                                   this.getHeight(node.right))
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left),
                                      this.getHeight(newRoot.right))
        return newRoot
      }
      
      addNode(value){
        this.root = this.addChild(this.root, value)
      }
      
      // 平衡因子,判断一个二叉树是否平衡
      getBalance(node) {
        return this.getBalance(node.left) - this.getBalance(node.right)
      }
      
      // 添加一个节点分为四种情况,分别为左子树的左节点,左子树的右节点,右子树的左节点,右子树的右节点。
      // 每种情况都要单独处理
      addChild(node, value) {
        if (!node) return new Node(value)
        if (node.value > value) {
          node.left = this.addChild(node.left, value)
        } else if (node.value, value) {
          node.right = this.addChild(node.right, value)
        } else {
          node.value = value
        }
        
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right))
        let balance = this.getBalance(node)
        
        // 左子树左节点,左子树高且左子树的左子树高,左子树可能平衡但整体树不平衡
        if(balance > 1 && this.getBalance(node.left) >= 0) {
          return this.rightRotate(node)
        }
        // 右子树右节点,右子树高且右子树的右子树高,右子树可能平衡,但整体不平衡
        if(balance < 1 && this.getBalance(node.right) <= 0) {
          return this.leftRotate(node)
        }
        // 左子树右节点,左子树高且左子树的右子树高,先左旋再右旋
        if(balance > 1 && this.getBalance(node.left) < 0) {
          node.left = this.leftRotate(node.left)
          return this.rightRotate(node)
        } 
        // 右子树左节点,右子树高且右子树的左子树高,先右旋再左旋
        if(balance < 1 && this.getBalance(node.right) > 0) {
          node.right = this.rightRotate(node.right)
          return this.leftRotate(node)
        }
        
        return node
      }
    }
    

    如果添加一个节点后,树还保持平衡就不做处理直接添加。

    添加节点之后就是删除节点。删除节点的操作也是类似的,首先删除节点,如果使用子树替换删除的节点,再判断树是否平衡,再经过一次或多次旋转后使树保持平衡。

    时间复杂度分析

    对于查找操作而言,二叉搜索树的时间复杂度介于O(log2N)到O(n)之间,如果退化成单链表,时间复杂度就是顺序查找,为O(n)。如果是平衡二叉树,查找效率会提高到O(log2N)。

    对于增加节点操作,二叉搜索树增加与查找的复杂度相同,而平衡二叉树在增加节点后,还可能进行额外的旋转操作。

    对于删除操作来说,二叉搜索树在查找的基础上可能会多一个最小后继节点替换操作,平衡二叉树还要在这个基础上增加一个可能的一次或多次树的旋转操作。

    展开全文
  • 平衡二叉树的实现我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:❝年轻人你不要过度消费我,这好吗?这不好。❞所以我们针对这个...

    平衡二叉树的实现

    我们在遍历二叉树时,先一直往左遍历,于是我们发现,当一棵树的每个节点都只有一个子节点时,他就变成了一个链表,然后链表就说啊:

    年轻人你不要过度消费我,这好吗?这不好。

    所以我们针对这个问题进行优化,就出现了「平衡二叉树」

    何为平衡,平衡是指,二叉树中任意节点的左右子树的高度差都不大于1。当插入或删除一个节点时,我们需要通过一次或多次树的「旋转」来保持二叉树的平衡。

    树的旋转分为「左旋」「右旋」两种具体操作,这两种操作是完全相反的,互为逆操作。

    左旋是「将该节点的右子树逆时针旋转」,右旋是「将该节点的左子树顺时针旋转」

    对于一个节点node进行左旋操作时,具体操作为:「将node.right子树取下,node.right节点称为新的根节点newRoot,将node接在newRoot的左节点,newRoot.left取下接在node的右节点上。」

    右旋操作相反:「将node.left子树取下,node.left节点作为新的根节点newRoot,将node接在newRoot的右节点,newRoot.right取下接在node的左节点上。」

    79aacbf014e103c24534581386345c00.png
    二叉树的左旋和右旋

    AVL插入节点有四种情况,分别为「左子树左节点,左子树右节点,右子树左节点,右子树右节点」

    0687e69ad1a44a6c425a1e9b268a6b21.png

    对于左子树左节点,进行一次右旋操作,右子树右节点,进行一次左旋操作可以恢复平衡。

    对于左子树右节点和右子树左节点需要两次旋转才能恢复平衡。

    代码实现:

    // 构造节点,使用节点的height属性判断是否平衡
    class Node {
      constructor(value) {
        this.value = value
        this.left = null
        this.right = null
        this.height = 1
      }
    }

    class AVL {
      constructor() {
        this.root = null
      }
      
      // 获取节点的高度
      getHeight(node) {
        if(!node) return 0
        return node.height
      }
      
      // 左旋的具体操作,将node节点的node.right取下,作为新的根节点,node.right.left取下
      // 将node接在node.right节点的左节点,node.right.left节点接在node的右节点
      leftRotate(node) {
        let newRoot = node.right
        let newNode = newRoot.left
        newRoot.left = node
        node.right = newNode
        node.height = 1 + Math.max(this.getHeight(node.left), 
                                   this.getHeight(node.right))
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left), 
                                      this.getHeight(newRoot.right))
        return newRoot
      }
      
      // 右旋的操作与左旋相反,将上述代码中的left换成right,right换成left就行
      rightRotate(node) {
        let newRoot = node.left
        let newNode = newRoot.right
        newRoot.right = node
        node.left = newNode
        node.height = 1 + Math.max(this.getHeight(node.left),
                                   this.getHeight(node.right))
        newRoot.height = 1 + Math.max(this.getHeight(newRoot.left),
                                      this.getHeight(newRoot.right))
        return newRoot
      }
      
      addNode(value){
        this.root = this.addChild(this.root, value)
      }
      
      // 平衡因子,判断一个二叉树是否平衡
      getBalance(node) {
        return this.getBalance(node.left) - this.getBalance(node.right)
      }
      
      // 添加一个节点分为四种情况,分别为左子树的左节点,左子树的右节点,右子树的左节点,右子树的右节点。
      // 每种情况都要单独处理
      addChild(node, value) {
        if (!node) return new Node(value)
        if (node.value > value) {
          node.left = this.addChild(node.left, value)
        } else if (node.value, value) {
          node.right = this.addChild(node.right, value)
        } else {
          node.value = value
        }
        
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right))
        let balance = this.getBalance(node)
        
        // 左子树左节点,左子树高且左子树的左子树高,左子树可能平衡但整体树不平衡
        if(balance > 1 && this.getBalance(node.left) >= 0) {
          return this.rightRotate(node)
        }
        // 右子树右节点,右子树高且右子树的右子树高,右子树可能平衡,但整体不平衡
        if(balance 1 && this.getBalance(node.right) <= 0) {
          return this.leftRotate(node)
        }
        // 左子树右节点,左子树高且左子树的右子树高,先左旋再右旋
        if(balance > 1 && this.getBalance(node.left) 0) {
          node.left = this.leftRotate(node.left)
          return this.rightRotate(node)
        } 
        // 右子树左节点,右子树高且右子树的左子树高,先右旋再左旋
        if(balance 1 && this.getBalance(node.right) > 0) {
          node.right = this.rightRotate(node.right)
          return this.leftRotate(node)
        }
        
        return node
      }
    }

    如果添加一个节点后,树还保持平衡就不做处理直接添加。

    添加节点之后就是删除节点。删除节点的操作也是类似的,首先删除节点,如果使用子树替换删除的节点,再判断树是否平衡,再经过一次或多次旋转后使树保持平衡。

    时间复杂度分析

    对于查找操作而言,二叉搜索树的时间复杂度介于O(log2N)到O(n)之间,如果退化成单链表,时间复杂度就是顺序查找,为O(n)。如果是平衡二叉树,查找效率会提高到O(log2N)。

    对于增加节点操作,二叉搜索树增加与查找的复杂度相同,而平衡二叉树在增加节点后,还可能进行额外的旋转操作。

    对于删除操作来说,二叉搜索树在查找的基础上可能会多一个最小后继节点替换操作,平衡二叉树还要在这个基础上增加一个可能的一次或多次树的旋转操作。

    展开全文
  • 平衡二叉树(1)由来:平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构;(2)特点:平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索...

    平衡二叉树

    (1)由来:平衡二叉树是基于二分法的策略提高数据的查找速度的二叉树的数据结构;

    (2)特点

    平衡二叉树是采用二分法思维把数据按规则组装成一个树形结构的数据,用这个树形结构的数据减少无关数据的检索,

    大大的提升了数据检索的速度;平衡二叉树的数据结构有以下规则:

    1.非叶子节点只能允许最多两个子节点的存在
    2.每一个非叶子节点数据分布规则为左边的子节点小当前节点的值,
    3.右边的子节点大于当前节点的值(这里值是基于自己的算法规则而定的,比如hash值);

    平衡树的层级结构

    因为平衡二叉树查询性能和树的层级(h高度)成正比、为了保证树的结构左右两端数据大致平衡降低二叉树的查询难度一般会采用一种算法机制实现节点数据结构的平衡

    实现了这种算法的有比如AVL、Treap、红黑树,使用平衡二叉树能保证数据的左右两边的节点层级相差不会大于 1

    通过这样避免树形结构由于删除增加变成线性链表影响查询效率,保证数据平衡的情况下查找数据的速度近于二分法查找;

    平衡二叉树特点

    1.非叶子节点最多拥有两个子节点;
    2.左边的子节点小当前节点的值
    3.右边的子节点大于当前节点的值
    4.树的左右两边的层级数相差不会大于 1 
    5.没有值相等重复的节点;
    6.具有二叉查找树的全部特性。

    二叉树的优点:二叉树详细步骤

    1.二叉排序树是一种比较有用的折衷方案。  
    2.数组的搜索比较方便,可以直接用下标,但删除或者插入某些元素就比较麻烦。  
    3.链表与之相反,删除和插入元素很快,但查找很慢。  
    4.二叉排序树就既有链表的好处,也有数组的好处。  
    5.在处理大批量的动态的数据是比较有用。

    平衡二叉树优点

    1.平衡二叉树伸展树(SplayTree)是一种二叉排序树,它能在O(logn)内完成插入、查找和删除操作
    2.平衡二叉树主要优点集中在快速查找

    二叉树插入如下图解

    图一就是一颗AVL树了,而图二则不是(节点右边标的是这个节点的高度)。

    089703007a2ef93a1931b2f0b435bf04.png

    2349c0aa8e6075eb951dd54ba962575f.png

    对于图二,因为节点9的左孩子高度为2,而右孩子高度为0。他们之间的差值超过1了。

    这种树就可以保证不会出现大量节点偏向于一边的情况了。

    当我们在进行节点插入的时候,可能会出现节点都倾向于左边的情况,例如:

    70007023160b02abd4583221807877ce.png

    我们把这种倾向于左边的情况称之为 左-左型。这个时候,我们就可以对节点 9 进行右旋操作,使它恢复平衡。

    2b3dc9fa5f73fcf9f2edc69d05de0d19.png

    即:顺时针旋转两个节点,使得父节点被自己的左孩子取代,而自己成为自己的右孩子

    再举个例子:

    f65f9883620e6dd70c4ba0048852054c.png

    节点4和9高度相差大于1。由于是左孩子的高度较高,此时是左-左型,进行右旋

    59e4f8088ebd138298f5bb9078435a2d.png

    这里要注意,节点4的右孩子成为了节点6的左孩子了

    04cd747bff797fdd5e335a68cd218666.gif

    左旋

    左旋和右旋一样,就是用来解决当大部分节点都偏向右边的时候,通过左旋来还原。例如:

    0e7e26b6282b7c7747ceb3e7569f4071.png

    我们把这种倾向于右边的情况称之为 右-右型

    823f3538e12cfb62de0f62e916d0b894.gif

    例子讲解:初始状态如下:

    fed275b237e5fcee8e616516cf9bb57b.png

    然后我们主键插入如下数值:1,4,5,6,7,10,9,8

    插入 1

    53f3d09f0a701cafcfae34a128474dd4.png

    左-左型,需要右旋调整。

    00c4ff677f8fa293a1366d044c0b4108.png

    插入4

    1a3071fed1305d2ec8cfb158e83b5a67.png

    继续插入 5

    760e7b495a525ee57488d252cc90663e.png

    右-右型,需要左旋转调整。

    4160c556ff8b3d9563ca74ecb566e51e.png

    继续插入6

    ffa7fe1871a1bff4c6c761de8f9e9d8a.png

    右-右型,需要进行左旋

    03c629a5cf9bb1bd66894742e192da5c.png

    继续插入7

    82f4aaebdf59c422fd369bb528b8e1ae.png

    右-右型,需要进行左旋

    a87ab1e21e37f3a115ce5e97516ee927.png

    继续插入10

    f27bcbfcb7bfb8bf5227cbcd73609726.png

    继续插入9

    3fb7a200810493eed7343fc3531191ee.png

    出现了这种情况怎么办呢?对于这种 右-左型 的情况,单单一次左旋或右旋是不行的,下面我们先说说如何处理这种情况,例如:

    d5663a5499b61f7c14a874f6a7592a38.png

    这种我们就把它称之为 右-左 型吧。处理的方法是先对节点10进行右旋把它变成右-右型

    649a8f7c08655b190445b59daf0d6a0e.png

    然后在进行左旋

    dcc3dfe50ca03b38ebecf0016141106d.png

    所以对于这种 右-左型的,我们需要进行一次右旋再左旋。

    同理,也存在 左-右型的,例如:

    973bd0d5fd2d73d34b20d68c00d12724.png

    对于左-右型的情况和刚才的 右-左型相反,我们需要对它进行一次左旋,再右旋。

    ed467d35c848a21ffbf700d1a0690021.png

    回到刚才那道题

    0991217f48d171683c0bc6fb557fcce7.png

    对它进行右旋再左旋。

    d4599eb5755b6a93862cd355b03b3ba4.png

    到此,我们的插入就结束了。

    失去平衡的调整方法

    • 解决失衡的方法口诀
      • 左左失衡,parent右旋;
      • 左右失衡,cur左旋,parent右旋;
      • 右右失衡,parent左旋;
      • 右左失衡,cur右旋,parent左旋;

    解析:parent为当前失衡的结点,cur为parent的孩子(新结点所在的子树的根节点)

    f1bfe7abebe907ab4da1efbd1b1d3e45.png
      • 四种失衡状态

    b0b9db793753dab6b4404ca34c6ca206.png

    2342c2e2c7d45c3dd1ce498f07df0fa3.png
      • 很明显:如果从根节点到新插入的结点是一路向左,即左左失衡;
      • 如果中途向右了,即左右失衡;
      • 如果一路向右,即为右右失衡;
      • 如果中途向左了,即右左失衡;
      • 根据不同的失衡,口诀中有不同的解决方法,接下来我们一起来验证一下吧:
        • ”左左失衡,parent右旋“:

    e91ffd4fb2986d2d1b4e1c5bb8b71cbb.png
      • “左右失衡,cur左旋,parent右旋”:

    8bf07e68542a45078d630a35c329437d.png
      • “右右失衡,parent左旋”:

    de6b2a8963a0e93e48bd1f96a2292f74.png
        • “右左失衡,cur右旋,parent左旋”:

    8cab84e8ee67ebcc0ae1a35aae8ff49d.png
    • 调整之后,该树还是一个平衡二叉树

    部分转载链接:https://blog.csdn.net/weixin_42125310/article/details/105183623

    展开全文
  • 在按照二叉查找树(二叉查找树(BST:Binary Search Tree) )的方式插入元素构建一个平衡二叉树(平衡二叉树 )时,可能会出现不平衡的现象。可以根据新插入节点与最低不平衡节点之间的位置关系进行相应的调整。我们先把...
  • 平衡二叉树对于初学者一直是一个比较复杂的知识点,因为其里面涉及到了大量的旋转操作。把大量的同学都给转晕了。这篇文章最主要的特点就是通过动画的形式演示。确保大家都能看懂。最后是手写一个平衡二叉树。一、...
  • 算法中包含了平衡二叉树的插入与删除算法,其中删除算法为本人独立编写。
  • 平衡二叉树删除结点的情况

    千次阅读 2019-03-04 12:59:12
    找到了要删除的结点 1.如果左右子树均不为空,且左子树比右子树高 找出结点的左子树中的最大结点 将最大结点的值赋值给该结点(左子树的父亲) 用结点的左子树的最大结点的值替换要删除的结点的值 这样做的用意是,...
  • 注意: ...这样修改之后就使得平衡二叉树好像和一般二叉树的操作比较,就是多了一个平衡操作。 3 删除操作情况很多,很困难,一定要理清思路。十分容易出bug的地方。 这里是查找后继节点的值,填补上到
  • 平衡二叉树的创建,RR旋转,LL旋转,RL旋转,LR旋转,插入、删除和一些其他操作。 平衡二叉树只是一种特殊的二叉排序树,其左右子树的高度差小于1。 左旋、右旋、左旋后右旋、右旋后左旋的理解:实际就是通过左右...
  • 平衡二叉树删除某个节点的方法

    千次阅读 2013-09-18 10:29:57
     首先我们找到待删除的节点Z,如果节点Z的两个孩子均为空,那么将其父节点中对应指向Z的指针置为空,然后删除节点Z。如果节点Z仅有一个孩子,那么将Z节点的父节点中指向Z的指针指向Z仅有的孩子,然后删除节点Z。...
  • AVL树算法,编程结构清晰,易于学习临摹。 欢迎下载。
  • 平衡二叉树(解惑) 平衡二叉树AVL(也是排序二叉树)失衡,分为左左(指在一个节点的左孩子的左孩子上插入节点(无论插得是左还是右节点)使二叉树失衡,就叫左左)、右右、左右、右左 调整平衡二叉树,可以通过...
  • 总结一下从平衡二叉树中删除结点可以分为以下三步:找到要删除的结点完成节点的删除找到因为删除而导致不满足平衡二叉树要求的子树并对其进行调整平衡二叉树删除的精髓在于,把要删除的结点数据与真正需要保留的结点...
  • 平衡二叉树删除

    千次阅读 多人点赞 2018-03-05 11:16:58
    平衡二叉树删除也涉及到删除后的连接问题。其删除一般分为4种情况: 1)删除叶子结点; 2)删除左子树为空,右子树不为空的结点: 3)删除左子树不为空,右子树为空的结点; 4)删除左右子树都不为空的结点。 ...
  • 平衡二叉树AVL删除

    2019-09-22 14:32:20
    平衡二叉树的插入过程:http://www.cnblogs.com/hujunzheng/p/4665451.html 对于二叉平衡树的删除采用的是二叉排序树删除的思路:  假设被删结点是*p,其双亲是*f,不失一般性,设*p是*f的左孩子,下面分三种情况...
  • 平衡二叉树 删除操作 C语言实现
  • 引言在上一篇《无死角“盘”它!...满足如下两个条件的二叉树称为“平衡二叉树”:首先它得是二分查找树然后它的左右子树的高度相差不超过1图1 平衡二叉树图2 非平衡二叉树图1就是一棵平衡二叉树,而图2不是...
  • 输入一棵二叉树,判断该二叉树是否是平衡二叉树平衡二叉树平衡二叉树(Balanced BinaryTree)又被称为AVL树。...但是由于其对二叉树施加了额外限制,因而其添加、删除操作都必须保证平衡二叉树的性子...
  • word 资料 平衡二叉树操作的演示 需求分析 本程序是利用平衡二叉树实现动态查找表的基本功能创建表查找插入删除 具体功能 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分裂六种操作供选择每种操作均提示...
  • 平衡二叉树

    千次阅读 多人点赞 2019-08-24 21:20:23
    平衡二叉树简介平衡二叉树(AVL)的定义平衡二叉树的单旋转双旋转代码Node类AVLTree类TestAVLTree类 简介 虽然搜索二叉树在查询,删除,添加上具有一定的优势,但是在一些情况下的效率也特别低。比如下面的这个搜索...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 2,793
精华内容 1,117
关键字:

平衡二叉树删除