精华内容
下载资源
问答
  • B树一般几千分叉,小的也有几分叉。 B树层数一般不多,几层左右(保证读盘次数尽可能少),每个节点表示一数据块,最小数据块大小为4K(跟硬盘结构有关)。从硬盘中读取一部分数据到内存,然后在内存...

    用于硬盘、U盘、操作系统、数据库等文件系统。
    B树一般几千个分叉,小的也有几百个分叉。
    在这里插入图片描述
    在这里插入图片描述
    B树层数一般不多,几层左右(保证读盘次数尽可能少),每个节点表示一个数据块,最小数据块大小为4K(跟硬盘结构有关)。从硬盘中读取一部分数据到内存,然后在内存中用红黑树操作。
    在这里插入图片描述

    展开全文
  • 当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。110. 平衡二叉树(简单)最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。题目描述给定一个二叉树,判断它是否是高度平衡的二叉树。 ...

    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。

    110. 平衡二叉树(简单)

    最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。

    题目描述

    给定一个二叉树,判断它是否是高度平衡的二叉树。
    
    本题中,一棵高度平衡二叉树定义为:
    
    一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
    
    示例 1:
    
    给定二叉树 [3,9,20,null,null,15,7]
    
        3
       / 
      9  20
        /  
       15   7
    返回 true 。
    
    示例 2:
    
    给定二叉树 [1,2,2,3,3,null,null,4,4]
    
           1
          / 
         2   2
        / 
       3   3
      / 
     4   4
    返回 false
    
    
    

    思路

    由于平衡二叉树定义为就是**一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。**用伪代码描述就是:

    if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉树 and root.right 也是平衡二叉树:
        print('是平衡二叉树')
    else:
        print('不是平衡二叉树')
    

    而 root.left 和 root.right 「如何判断是否是二叉平衡树就和 root 是一样的了」,可以看出这个问题有明显的递归性。

    因此我们首先需要知道如何计算一个子树的高度。这个可以通过递归的方式轻松地计算出来。计算子树高度的 Python 代码如下:

    def dfs(node, depth):
        if not node: return 0
        l = dfs(node.left, depth + 1)
        r = dfs(node.right, depth + 1)
        return max(l, r) + 1
    

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:
        def isBalanced(self, root: TreeNode) -> bool:
            def dfs(node, depth):
                if not node: return 0
                l = dfs(node.left, depth + 1)
                r = dfs(node.right, depth + 1)
                return max(l, r)  + 1
            if not root: return True
            if abs(dfs(root.left, 0) -  dfs(root.right, 0)) > 1: return False
            return self.isBalanced(root.left) and self.isBalanced(root.right)
    

    「复杂度分析」

    • 时间复杂度:对于 isBalanced 来说,由于每个节点最多被访问一次,这部分的时间复杂度为
      ,而 dfs 函数 每次被调用的次数不超过
      ,因此总的时间复杂度为
      ,其中
      为 树的节点总数。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为
      ,其中
      为树的高度。

    108. 将有序数组转换为二叉搜索树(简单)

    108 和 109 基本是一样的,只不过数据结构不一样,109 变成了链表了而已。由于链表操作比数组需要考虑更多的因素,因此 109 是 中等难度。

    题目描述

    将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
    
    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    
    示例:
    
    给定有序数组: [-10,-3,0,5,9],
    
    一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
    
          0
         / 
       -3   9
       /   /
     -10  5
    
    

    思路

    对于这个问题或者 给定一个二叉搜索树,将其改为平衡(后面会讲) 基本思路都是一样的。

    题目的要求是将有序数组转化为:

    1. 高度平衡的二叉树
    2. 二叉搜索树

    由于平衡二叉树是左右两个子树的高度差的绝对值不超过 1。因此一种简单的方法是**选择中点作为根节点,根节点左侧的作为左子树,右侧的作为右子树即可。**原因很简单,这样分配可以保证左右子树的节点数目差不超过 1。因此高度差自然也不会超过 1 了。

    上面的操作同时也满足了二叉搜索树,原因就是题目给的数组是有序的。

    ❝ 你也可以选择别的数作为根节点,而不是中点,这也可以看出答案是不唯一的。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:
        def sortedArrayToBST(self, nums: List[int]) -> TreeNode:
            if not nums: return None
            mid = (len(nums) - 1) // 2
            root = TreeNode(nums[mid])
            root.left = self.sortedArrayToBST(nums[:mid])
            root.right = self.sortedArrayToBST(nums[mid + 1:])
            return root
    

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为
      ,其中
      为数组长度。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为
      ,其中
      为树的高度。同时由于是平衡二叉树,因此
      就是

    109. 有序链表转换二叉搜索树(中等)

    题目描述

    `给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。
    
    本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
    
    示例:
    
    给定的有序链表: [-10, -3, 0, 5, 9],
    
    一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:
    
          0
         / 
       -3   9
       /   /
     -10  5
    
    

    思路

    和 108 思路一样。 不同的是数据结构的不同,因此我们需要关注的是链表和数组的操作差异。

    47bebe7884e7cf05aeb27b51f6f5f5a7.png

    (数组的情况)

    我们再来看下链表:

    c2f6f62713a4fbc04e7356841cbdff59.png

    (链表的情况)

    找到中点,只需要使用经典的快慢指针即可。同时为了防止环的出现, 我们需要斩断指向 mid 的 next 指针,因此需要记录一下中点前的一个节点,这只需要用一个变量 pre 记录即可。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:
        def sortedListToBST(self, head: ListNode) -> TreeNode:
            if not head:
                return head
            pre, slow, fast = None, head, head
    
            while fast and fast.next:
                fast = fast.next.next
                pre = slow
                slow = slow.next
            if pre:
                pre.next = None
            node = TreeNode(slow.val)
            if slow == fast:
                return node
            node.left = self.sortedListToBST(head)
            node.right = self.sortedListToBST(slow.next)
            return node
    

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为
      ,其中
      为链表长度。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为
      ,其中
      为树的高度。同时由于是平衡二叉树,因此
      就是

    1382. 将二叉搜索树变平衡(中等)

    题目描述

    给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。
    
    如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。
    
    如果有多种构造方法,请你返回任意一种。
    
     
    
    示例:
    
    

    070ea097457416b9540493f3f85f6727.png
    输入:root = [1,null,2,null,3,null,4,null,null]
    输出:[2,1,3,null,null,null,4]
    解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。
     
    
    提示:
    
    树节点的数目在 1 到 10^4 之间。
    树节点的值互不相同,且在 1 到 10^5 之间。
    
    

    思路

    由于二叉搜索树的中序遍历是一个有序数组,因此问题很容易就转化为 108. 将有序数组转换为二叉搜索树(简单)

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:
        def inorder(self, node):
            if not node: return []
            return self.inorder(node.left) + [node.val] + self.inorder(node.right)
        def balanceBST(self, root: TreeNode) -> TreeNode:
            nums = self.inorder(root)
            def dfs(start, end):
                if start == end: return TreeNode(nums[start])
                if start > end: return None
                mid = (start + end) // 2
                root = TreeNode(nums[mid])
                root.left = dfs(start, mid - 1)
                root.right = dfs(mid + 1, end)
                return root
            return dfs(0, len(nums) - 1)
    

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为
      ,其中
      为链表长度。
    • 空间复杂度:虽然使用了递归,但是瓶颈不在栈空间,而是开辟的长度为
      的 nums 数组,因此空间复杂度为
      ,其中
      为树的节点总数。

    总结

    本文通过四道关于二叉平衡树的题帮助大家识别此类型题目背后的思维逻辑,我们来总结一下学到的知识。

    平衡二叉树指的是:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

    如果需要让你判断一个树是否是平衡二叉树,只需要死扣定义,然后用递归即可轻松解决。

    如果需要你将一个数组或者链表(逻辑上都是线性的数据结构)转化为平衡二叉树,只需要随便选一个节点,并分配一半到左子树,另一半到右子树即可。

    同时,如果要求你转化为平衡二叉搜索树,则可以选择排序数组(或链表)的中点,左边的元素为左子树, 右边的元素为右子树即可。

    ❝ 小提示 1: 如果不需要是二叉搜索树则不需要排序,否则需要排序。

    ❝ 小提示 2: 你也可以不选择中点, 算法需要相应调整,感兴趣的同学可以试试。

    ❝ 小提示 3: 链表的操作需要特别注意环的存在。
    展开全文
  • 当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。110. 平衡二叉树(简单)最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。题目描述给定一个二叉树,判断它是否是高度平衡的二叉树。本题...

    力扣关于平衡二叉树的题目还是有一些的,并且都非常经典,推荐大家练习。今天给大家精选了 4 道题,如果你彻底搞明白了这几道题,碰到其他的平衡二叉树的题目应该不至于没有思路。当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。

    110. 平衡二叉树(简单)

    最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。

    题目描述

    给定一个二叉树,判断它是否是高度平衡的二叉树。本题中,一棵高度平衡二叉树定义为:一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。示例 1:给定二叉树 [3,9,20,null,null,15,7]    3   /   9  20    /     15   7返回 true 。示例 2:给定二叉树 [1,2,2,3,3,null,null,4,4]       1      /      2   2    /    3   3  /  4   4返回 false

    思路

    由于平衡二叉树定义为就是**一个二叉树每个节点的左右两个子树的高度差的绝对值不超过 1。**用伪代码描述就是:

    if abs(高度(root.left) - 高度(root.right)) <= 1 and root.left 也是平衡二叉树 and root.right 也是平衡二叉树:    print('是平衡二叉树')else:    print('不是平衡二叉树')

    而 root.left 和 root.right 「如何判断是否是二叉平衡树就和 root 是一样的了」,可以看出这个问题有明显的递归性。

    因此我们首先需要知道如何计算一个子树的高度。这个可以通过递归的方式轻松地计算出来。计算子树高度的 Python 代码如下:

    def dfs(node, depth):    if not node: return 0    l = dfs(node.left, depth + 1)    r = dfs(node.right, depth + 1)    return max(l, r) + 1

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:    def isBalanced(self, root: TreeNode) -> bool:        def dfs(node, depth):            if not node: return 0            l = dfs(node.left, depth + 1)            r = dfs(node.right, depth + 1)            return max(l, r)  + 1        if not root: return True        if abs(dfs(root.left, 0) -  dfs(root.right, 0)) > 1: return False        return self.isBalanced(root.left) and self.isBalanced(root.right)

    「复杂度分析」

    • 时间复杂度:对于 isBalanced 来说,由于每个节点最多被访问一次,这部分的时间复杂度为 ,而 dfs 函数 每次被调用的次数不超过 ,因此总的时间复杂度为 ,其中 为 树的节点总数。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 ,其中 为树的高度。

    108. 将有序数组转换为二叉搜索树(简单)

    108 和 109 基本是一样的,只不过数据结构不一样,109 变成了链表了而已。由于链表操作比数组需要考虑更多的因素,因此 109 是 中等难度。

    题目描述

    将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定有序数组: [-10,-3,0,5,9],一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:      0     /    -3   9   /   / -10  5

    思路

    对于这个问题或者 给定一个二叉搜索树,将其改为平衡(后面会讲) 基本思路都是一样的。

    题目的要求是将有序数组转化为:

    1. 高度平衡的二叉树
    2. 二叉搜索树

    由于平衡二叉树是左右两个子树的高度差的绝对值不超过 1。因此一种简单的方法是**选择中点作为根节点,根节点左侧的作为左子树,右侧的作为右子树即可。**原因很简单,这样分配可以保证左右子树的节点数目差不超过 1。因此高度差自然也不会超过 1 了。

    上面的操作同时也满足了二叉搜索树,原因就是题目给的数组是有序的。

    你也可以选择别的数作为根节点,而不是中点,这也可以看出答案是不唯一的。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:    def sortedArrayToBST(self, nums: List[int]) -> TreeNode:        if not nums: return None        mid = (len(nums) - 1) // 2        root = TreeNode(nums[mid])        root.left = self.sortedArrayToBST(nums[:mid])        root.right = self.sortedArrayToBST(nums[mid + 1:])        return root

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 ,其中 为数组长度。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 ,其中 为树的高度。同时由于是平衡二叉树,因此 就是 。

    109. 有序链表转换二叉搜索树(中等)

    题目描述

    `给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定的有序链表: [-10, -3, 0, 5, 9],一个可能的答案是:[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树:      0     /    -3   9   /   / -10  5

    思路

    和 108 思路一样。 不同的是数据结构的不同,因此我们需要关注的是链表和数组的操作差异。

    53b1379099bed215851ff9e29b6473d5.png

    (数组的情况)

    我们再来看下链表:

    5883e1b6f2388d902b8cd0837c38be06.png

    (链表的情况)

    找到中点,只需要使用经典的快慢指针即可。同时为了防止环的出现, 我们需要斩断指向 mid 的 next 指针,因此需要记录一下中点前的一个节点,这只需要用一个变量 pre 记录即可。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:    def sortedListToBST(self, head: ListNode) -> TreeNode:        if not head:            return head        pre, slow, fast = None, head, head        while fast and fast.next:            fast = fast.next.next            pre = slow            slow = slow.next        if pre:            pre.next = None        node = TreeNode(slow.val)        if slow == fast:            return node        node.left = self.sortedListToBST(head)        node.right = self.sortedListToBST(slow.next)        return node

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 ,其中 为链表长度。
    • 空间复杂度:由于使用了递归,这里的空间复杂度的瓶颈在栈空间,因此空间复杂度为 ,其中 为树的高度。同时由于是平衡二叉树,因此 就是 。

    1382. 将二叉搜索树变平衡(中等)

    题目描述

    给你一棵二叉搜索树,请你返回一棵 平衡后 的二叉搜索树,新生成的树应该与原来的树有着相同的节点值。如果一棵二叉搜索树中,每个节点的两棵子树高度差不超过 1 ,我们就称这棵二叉搜索树是 平衡的 。如果有多种构造方法,请你返回任意一种。 示例:
    0d79ecda16227aba37d7e8e4f70cee06.png
    输入:root = [1,null,2,null,3,null,4,null,null]输出:[2,1,3,null,null,null,4]解释:这不是唯一的正确答案,[3,1,4,null,2,null,null] 也是一个可行的构造方案。 提示:树节点的数目在 1 到 10^4 之间。树节点的值互不相同,且在 1 到 10^5 之间。

    思路

    由于二叉搜索树的中序遍历是一个有序数组,因此问题很容易就转化为 108. 将有序数组转换为二叉搜索树(简单)。

    代码

    代码支持: Python3

    Python3 Code:

    class Solution:    def inorder(self, node):        if not node: return []        return self.inorder(node.left) + [node.val] + self.inorder(node.right)    def balanceBST(self, root: TreeNode) -> TreeNode:        nums = self.inorder(root)        def dfs(start, end):            if start == end: return TreeNode(nums[start])            if start > end: return None            mid = (start + end) // 2            root = TreeNode(nums[mid])            root.left = dfs(start, mid - 1)            root.right = dfs(mid + 1, end)            return root        return dfs(0, len(nums) - 1)

    「复杂度分析」

    • 时间复杂度:由于每个节点最多被访问一次,因此总的时间复杂度为 ,其中 为链表长度。
    • 空间复杂度:虽然使用了递归,但是瓶颈不在栈空间,而是开辟的长度为 的 nums 数组,因此空间复杂度为 ,其中 为树的节点总数。

    总结

    本文通过四道关于二叉平衡树的题帮助大家识别此类型题目背后的思维逻辑,我们来总结一下学到的知识。

    平衡二叉树指的是:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1。

    如果需要让你判断一个树是否是平衡二叉树,只需要死扣定义,然后用递归即可轻松解决。

    如果需要你将一个数组或者链表(逻辑上都是线性的数据结构)转化为平衡二叉树,只需要随便选一个节点,并分配一半到左子树,另一半到右子树即可。

    同时,如果要求你转化为平衡二叉搜索树,则可以选择排序数组(或链表)的中点,左边的元素为左子树, 右边的元素为右子树即可。

    小提示 1: 如果不需要是二叉搜索树则不需要排序,否则需要排序。

    小提示 2: 你也可以不选择中点, 算法需要相应调整,感兴趣的同学可以试试。

    小提示 3: 链表的操作需要特别注意环的存在。

    展开全文
  • 今天要介绍种高级数据结构AVL树,介绍之前AVL,会先说明平衡二叉树,并将树的学习路线进行总结,并介绍维持平衡的方法:右旋转、左旋转。 一、树学习路线 1、路线总结 总结了一下树的学习路线,如下图: 2、...

    f36ce9e40bc50646f6f9fabaf2f40d08.png

    今天要介绍几种高级数据结构AVL树,介绍之前AVL,会先说明平衡二叉树,并将树的学习路线进行总结,并介绍维持平衡的方法:右旋转、左旋转。

      一、树学习路线

      1、路线总结

      总结了一下树的学习路线,如下图:

    7d3916d4fddfa2db629c2360fb015774.png

      2、说明

      上面这个图要从上往下进行一步一步学习;首先,从二叉树开始学习,要对树的一些概念有一些基本了解,如树的左孩子和右孩子等,然后对树的遍历方法:先序、中序和后序遍历都熟练掌握,有精力再把层序遍历掌握;

      接下来,大部分的树,都是在二叉树的基础上加了许多特性而形成的,所以二叉树是基础,如二叉搜索树,任意一个节点都比左子树大,都比右子树小,主要用于解决查找问题,对二分查找法有一个基本了解,还有一个特性,二分搜索树的中序遍历:数据就从从小到大进行排序了。

      AVL树,是今天要讲的话题,下面会详细进行讲解。

      红黑树应该是大名鼎鼎了,都应该听过了,之后我会专门介绍。

      trie树就不再是二叉树了,是多叉树了,之后也会讲解。

      二、平衡二叉树

      1、定义

      平衡二叉树,首先是二叉树,并且对于任意一个节点,左子树和右子树的高度差不能超过1。

      2、意义

      有了二分查找树为什么还要平衡二叉树呢?这篇对二分查找树进行了详细介绍,并对先序、中序和后序进行了明确说明,可以参考:https://www.cnblogs.com/liudw-0215/p/9835691.html,因为二叉树有一个弊端就是会退化为链表,就是只有左子树或右子树有节点,这样查询效率就会变低了。所以,就需要“平衡”这个概念了。

      3、平衡因子

      先画个图,进行说明,不是平衡二叉树,只是为了说明问题,如下图:

    20b10cb457a0f19c762f396b770c6cdb.png

      说明:如上图,树的高度从叶子节点开始,并且叶子节点高度是1;平衡因子就是用左子树高度减去右子树高度,例如:4这个节点,左子树2的高度为1,右子树没有则为0,所以4这个节点的平衡因子为1。

      三、AVL树

      1、定义

        AVL树是自平衡二分搜索树,既具有平衡性和二分性。

       2、构建AVL树类

        是在二分搜索树的基础上进行修改并维持“平衡”这个特性的,首先,来看下AVL树的类,如下:

    #ifndef AVLTREE_AVLTREE_H
    #define AVLTREE_AVLTREE_H
    
    #include <algorithm>
    #include <iostream>
    #include <vector>
    
    template<typename Key, typename Value>
    class AVLTree {
    private:
        struct Node {
            Key key;
            Value value;
            Node *left;
            Node *right;
            int height;    //用于标注高度,计算平衡因子
    
            Node(Key key, Value value) {
                this->key = key;
                this->value = value;
                this->left = this->right = nullptr;
                height = 1;
            }
    
            Node(Node *node) {
                this->key = node->key;
                this->value = node->value;
                this->left = node->left;
                this->right = node->right;
                this->height = node->height;
            }
        };
    
        Node *root;
        int size;
    
    public:
    
        AVLTree() {
            root = nullptr;
            size = 0;
        }
    
        ~AVLTree() {
            destroy(root);
        }
    
        int getSize() {
            return size;
        }
    
        int isEmpty() {
            return size == 0;
        }
        
        int getHeight(Node *node) {    //获取高度
            if (node == nullptr) {
                return 0;
            }
            return node->height;
        }
    
        int getBalanceFactor(Node *node) {    //获取平衡因子
            if (node == nullptr) {
                return 0;
            }
            return getHeight(node->left) - getHeight(node->right);
        }
    
        bool isBST() {
            std::vector<Key> keys;
            inOrder(root, keys);
            for (int i = 1; i < keys.size(); ++i) {
                if (keys.at(i - 1) < keys.at(i)) {
                    return false;
                }
            }
            return true;
        }
    
        bool isBalanced() {
            return isBalanced(root);
        }
    
        void add(Key key, Value value) {
            root = add(root, key, value);
        }
    
        bool contains(Key key) {
            return getNode(root, key) != nullptr;
        }
    
        Value *get(Key key) {
            Node *node = getNode(root, key);
            return node == nullptr ? nullptr : &(node->value);
        }
    
        void set(Key key, Value newValue) {
            Node *node = getNode(root, key);
            if (node != nullptr) {
                node->value = newValue;
            }
        }
    
        // 从二叉树中删除键值为key的节点
        Value *remove(Key key) {
            Node *node = getNode(root, key);
            if (node != nullptr) {
                root = remove(root, key);
                return &(node->value);
            }
            return nullptr;
        }
    
    private:
    
        // 向以node为根的二叉搜索树中,插入节点(key, value)
        // 返回插入新节点后的二叉搜索树的根
        Node *add(Node *node, Key key, Value value) {
            if (node == nullptr) {
                size++;
                return new Node(key, value);
            }
            if (key == node->key) {
                node->value = value;
            } else if (key < node->key) {
                node->left = add(node->left, key, value);
            } else {
                node->right = add(node->right, key, value);
            }
            node->height = 1 + std::max(getHeight(node->left), getHeight(node->right));
            int balanceFactor = getBalanceFactor(node);
            if (std::abs(balanceFactor) > 1) {
                std::cout << "unbalanced : " << balanceFactor;
            }
            return node;
        }
    
        // 在以node为根的二叉搜索树中查找key所对应的Node
        Node *getNode(Node *node, Key key) {
            if (node == nullptr) {
                return nullptr;
            }
            if (key == node->key) {
                return node;
            } else if (key < node->key) {
                return getNode(node->left, key);
            } else {
                return getNode(node->right, key);
            }
        }
    
        void destroy(Node *node) {
            if (node != nullptr) {
                destroy(node->left);
                destroy(node->right);
                delete node;
                size--;
            }
        }
    
        // 在以node为根的二叉搜索树中,返回最小键值的节点
        Node *minimum(Node *node) {
            if (node->left == nullptr)
                return node;
            return minimum(node->left);
        }
    
        // 在以node为根的二叉搜索树中,返回最大键值的节点
        Node *maximum(Node *node) {
            if (node->right == nullptr)
                return node;
            return maximum(node->right);
        }
    
        // 删除掉以node为根的二分搜索树中的最小节点
        // 返回删除节点后新的二分搜索树的根
        Node *removeMin(Node *node) {
            if (node->left == nullptr) {
                Node *rightNode = node->right;
                delete node;
                size--;
                return rightNode;
            }
    
            node->left = removeMin(node->left);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中的最大节点
        // 返回删除节点后新的二分搜索树的根
        Node *removeMax(Node *node) {
            if (node->right == nullptr) {
                Node *leftNode = node->left;
                delete node;
                size--;
                return leftNode;
            }
    
            node->right = removeMax(node->right);
            return node;
        }
    
        // 删除掉以node为根的二分搜索树中键值为key的节点
        // 返回删除节点后新的二分搜索树的根
        Node *remove(Node *node, Key key) {
            if (node == nullptr) {
                return nullptr;
            }
            if (key < node->key) {
                node->left = remove(node->left, key);
                return node;
            } else if (key > node->key) {
                node->right = remove(node->right, key);
                return node;
            } else {
                if (node->left == nullptr) {
                    Node *rightNode = node->right;
                    delete node;
                    size--;
                    return rightNode;
                }
    
                if (node->right == nullptr) {
                    Node *leftNode = node->left;
                    delete node;
                    size--;
                    return leftNode;
                }
    
                Node *successor = new Node(minimum(node->right));
                //Node *precursor = new Node(maximum(node->right));
                size++;
    
                successor->right = removeMin(node->right);
                successor->left = node->left;
                //precursor->left = removeMax(node->left);
                //precursor->right = node->right;
    
                delete node;
                size--;
    
                return successor;
                //return precursor;
            }
        }
    
        void inOrder(Node *node, std::vector<Key> keys) {
            if (node == nullptr) {
                return;
            }
            inOrder(node->left, keys);
            keys.push_back(node->key);
            inOrder(node->right, keys);
        }
    
        bool isBalanced(Node *node) {
            if (node == nullptr) {
                return true;
            }
    
            int balanceFactor = getBalanceFactor(node);
            if (std::abs(balanceFactor) > 1) {
                return false;
            }
    
            return isBalanced(node->left) && isBalanced(node->right);
        }
    };
    
    #endif //AVLTREE_AVLTREE_H

      增加height属性,用于记录每个节点的高度,并计算平衡因子;

      3、获取节点高度

      把height属性返回就可以了:

    int getHeight(Node *node) {    //获取高度
            if (node == nullptr) {
                return 0;
            }
            return node->height;
        }

      4、获取平衡因子

      将左子树高度减去右子树高度即可,但注意:不要区绝对值,因为之后的旋转要判断左子树还是右子树的高度高,代码如下:

     int getBalanceFactor(Node *node) {    //获取平衡因子
            if (node == nullptr) {
                return 0;
            }
            return getHeight(node->left) - getHeight(node->right);
        }

      5、判断是不是平衡二叉树

      平衡因子大于1就不是平衡二叉树了,代码如下:

     bool isBalanced(Node *node) {
            if (node == nullptr) {
                return true;
            }
    
            int balanceFactor = getBalanceFactor(node);
            if (std::abs(balanceFactor) > 1) {
                return false;
            }
    
            return isBalanced(node->left) && isBalanced(node->right);
        }
    
    bool isBalanced() {
            return isBalanced(root);
        }

      四、AVL树的旋转

       1、什么时维护平衡?

      如下图,假如原来没有2这个节点,那么树是平衡二叉树,但插入2之后,就不再平衡了,这时就需要维护平衡了,大体上有4种情况需要维护平衡,来说明这一种。

    20b10cb457a0f19c762f396b770c6cdb.png

        2、右旋转 LL

        将其中的部分节点抽离出来,如下图:

    803e3ea4edfa4ce7ed9bb3a8d17548a0.png

      说明:主要分为两步:

      第一步:将T3保存,然后将y以及孩子节点旋转到x的右孩子位置,相对于x,y是顺时针向右旋转的,所以叫右旋转;

      第二步:将T3移到y的左孩子位置

      最后,形成的二叉树符合二分和平衡两个性质,所以还是平衡二叉树。

      3、右旋转代码实现

      上图应该已经讲解的很明白了吧,代码如下:

     Node *rightRotate(Node *y) {
            Node *x = y->left;    //存x
            Node *tmp = x->right;    //将x的右孩子备份
            x->right = y;    //将y右旋转到x的右孩子
            y->left = tmp;    //将x的右孩子移到y的左侧
            y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;    //修改y高度,注意要先修改y的高度
            x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;    //修改x的高度
            return x;
        }

      4、左旋转 RR

      左旋转和右旋转很相似,只是方向不同,如下图:

    9199d9ee51f44d93d2c5c4dcc80022eb.png

      说明:相对于x,y是逆时针向左旋转,所以是左旋转

      5、左旋转代码实现

      左旋转代码跟右旋转很相似,代码如下:

     Node *leftRotate(Node *y){
            Node *x = y->right;
            Node *tmp = x->left;
            x->left = y;
            y->right = tmp;
            y->height = std::max(getHeight(y->left), getHeight(y->right)) + 1;
            x->height = std::max(getHeight(x->left), getHeight(x->right)) + 1;
            return x;
        }

      6、LR

      还有两种情况需要讨论,LL代表“左左”,LR代表“左右”,如下图:

    d52f91129d4cad6020123439bd66aadc.png

      说明:借助左旋转将LR转为LL,再对LL进行右旋转就OK了,所以理解左、右旋转是基础!

      7、LR代码实现

      代码如下:

    if (balanceFactor > 1 && getBalanceFactor(node->left) < 0) {    //LR
                node->left = leftRotate(node->left);
                return rightRotate(node);
            }

      8、RL

      最后一种情况RL,如下图:

    2194bc7c0895d58aa9c3484c614ffd2d.png

      9、RL代码实现

      代码如下:

     f (balanceFactor < -1 && getBalanceFactor(node->right) > 0) {    //RL
                node->right = rightRotate(node->right);
                return leftRotate(node);
            }

      总结

      AVL树和平衡二叉树就比较难了,主要理解右旋转和左旋转,对之后理解红黑树有巨大作用!

    展开全文
  • 当你领会了我的思路之后, 建议再找几个题目练手,巩固一下学习成果。 110. 平衡二叉树(简单) 最简单的莫过于判断一个树是否为平衡二叉树了,我们来看下。 题目描述 给定一个二叉树,判断它是否是高度平衡的二叉树...
  • 1.节点的删除 ...对于删除的节点有不为空的叶子节点,这种情况最为复杂,需要平衡调整。 删除节点平衡调整的情况有如下种 待删除节点的兄弟节点是红色 待删除节点的兄弟节点是黑色,且兄弟...
  • 破坏平衡的几种情况 这是第一种情况,其中A节点和B节点只是平衡二叉树的某一个子集合,要想打破这个平衡,那么插入的节点C必然...打破平衡后,经过一系列操作达到平衡,由以上可知,大致有几种情况,可大致分为..
  • 目录一、满二叉树二、完全二叉树三、二叉排序树四、平衡二叉树 一、满二叉树 ...若双亲,双亲节点编号 = ⌊i/2⌋ 若左孩子,左孩子编号 = 2*i 若右孩子,右孩子编号 = 2*i + 1 二、完全二叉树 定义 高
  • 平衡二叉树

    2015-01-04 22:25:44
    [cpp] view ...//首先分析了这种旋转,发现都和平衡因子关系,当一结点平衡因子为2的时候,就该旋转了。  /*左旋之后,K1子节点的右枝上如果结点给予K2,左枝上的结点保持不变;   右
  • 话说这系列鸽了好久,之前在准备语言考试,就没管博客了,现在暑假咱们继续上路! 每当我们进行一次插入之后,整棵AVL树的平衡性就有可能发生改变,为了...考虑一下产生不平衡有几种情况,稍加思索就会明白...
  • 树的度:找到分支最多的节点,这个节点有多少分支,这棵树的度就为。 分支最多的节点为D,它有三分支 这棵树的度为3 深度 树的深度就是树的层数 深度为4 根节点与叶子节点 叶子节点:没有子节点的节点 这棵树的...
  • 平衡二叉树(Balanced Binary Tree)又被称为AVL树(别于AVL算法),且具有以下性质:它是一 棵空树或它的左右两子树的高度差的绝对值不超过1,并且左右两子树都是一棵平衡二叉树(递归定义)的二叉排序树。...
  • 二叉平衡树(AVL树)

    2020-10-07 18:54:34
    从上面简单的定义我们可以得出几个重要的信息: 平衡二叉树又称AVL树 平衡二叉树必须是二叉排序树 每个节点的左子树和右子树的高度差至多为1。 树的高度和深度本质区别:深度是从根节点数到它的叶节点,高度是从叶...
  • 只有在一开始,第几个点就是几号店。。。在进行翻转后,如果还要翻转l-r,不是对l节点和r节点进行操作,而是对第l个和第r个点进行翻转。首先,如果我们对整个序列建立平衡树,因为没有节点的增加和减少,所以整个数...
  • 5.5.2平衡二叉树

    2020-09-24 19:47:06
    其实之前我简单了解过,首先我们先来回忆一下平方差数到几个概念,平方差数也称为avl数,它是任意节点平衡因子,绝对值不超过1的二茬数,那么什么是平衡因子呢?平分因子,其实左子数高度与柚子数高度的差,大家要...
  • 树的每个节点都拥有2个以上的节点,每个节点能存更多数据,有几个节点就叫几阶B树 B+树 只有树的叶子节点存数据(顺序存储),其余节点只存键值 聚集索引 以数据库表的主键做为树索引键值 非聚集索引 以非...
  • PS:今天上午,非常郁闷,很多简略基础的问题搞得我有些迷茫,哎,代码天不写就忘。... 二叉树的定义:每个节点至多俩颗子树(即二叉树中不存在度大于2的节点),并且,二叉树的子树阁下之分,其次...
  • 平衡树 || Red-Black Tree

    2016-11-01 03:40:39
    红黑树 是一种 平衡二叉搜索树, 这里的平衡和我们之前说的AVL树的平衡有一点不一样,AVL的平衡是任意节点的子树 的高度差不能大于1. 但是红黑树的平衡是对于他... 每个节点有两种颜色 红色或者黑色  2. 根节点是黑色的
  • 天写了写了道题,觉得这道平衡二叉树的题有点意思,就把他的c#算法写出来,不足之处请大家指点。 先看题目: 平衡二叉树 难 度 等 级: ...求n个节点有m叶子节点的平衡二叉树数 (0 例如:
  • Treap是一棵二叉搜索树(自然满足二叉搜索树的性质),同时节点有rand出来的key值,根据这key值treap同时还是一堆。 https://baike.baidu.com/item/Treap 这是百度百科的链接,具体原理可以参考 我们都...
  • (三) 红黑树 红黑树 自身具有优秀的平衡性,具有很高效的检索速度,很适于对权重的数据进行组织和查找。...红黑树的每个节点(node)至少包括了5域:父节点指针、左孩子指针、右孩子指针、关键字...
  • 先看几个基本概念:  树:由根出发,指向n个孩子,孩子再指向孙子。。。这样一种数据结构  二叉树:每个接点最多两个孩子的树  二叉查找树:每个结点的左子树  平衡二叉树:每个结点左右子树的高度差不...
  • 小知识点:树的高度指的是这有几层,树的深度有人规定根节点为0层也有人规定根节点为第一层,所以树的高度和深度有可能不一样 ① 设计函数计算树的高度 ② 递归检查子树是否也为平衡二叉树 2. 代码 # -*- coding...
  • 也就是说,树的一条分支会很多层,而其他的分支却只有层, 这会造成很大的性能问题 所以需要平衡二叉搜索树来解决这问题 平衡二叉树的概念 在AVL 树中,需要对每个节点计算右子树高度(hr)和左子树高度(hl...
  • 首先以最基本的二叉树开始,由浅入深,逐渐了解各个算法的优缺点适用...一、二叉树二叉树可以分为以下种: 普通二叉树 满二叉树 完全二叉树(1)普通二叉树 由一节点加上两棵分别称为左子树和右子树组成(2...
  • Kd-树概念Kd-树 其实是K-dimension tree的缩写,是对数据点在k维空间中划分的一种数据...为了能有效的找到最近邻,Kd-树采用分而治之的思想,即将整个空间划分为几个小部分。六个二维数据点生成的Kd-树的图为:2D ...
  • 平衡树之splay讲解

    2013-12-08 23:21:00
    首先来说是splay是二叉搜索树,它可以说是线段树和SBT的综合,更可以解决一些二者解决不了的问题,splay几乎所有的操作都是由splay这一操作完成的,在介绍这一操作前我们先介绍几个概念和定义  二叉搜索树,即BST...

空空如也

空空如也

1 2 3 4 5 ... 14
收藏数 278
精华内容 111
关键字:

平衡节点有几个