美文网首页
树结构-1

树结构-1

作者: 杭拼小何 | 来源:发表于2020-08-11 10:56 被阅读0次

    1.二叉搜索树、平衡二叉树
    2.平衡二叉树之红黑树、
    3.B 树、B+树、B* 树、
    4.字典树 ( Trie树 )

    二叉搜索树(又名二叉排序树)

    特点:
    1.左子树上的节点均小于根节点
    2.右子树上的节点均大于根节点

    二叉搜索树

    二叉平衡树

    为什么要有二叉平衡树,二叉搜索树的结构与值的插入顺序有关,同一组数,若其元素的插入顺序不同,二叉搜索树的结构是千差万别的。举个例子,给出一组数[1,3,5,8,9,13]

    若按照[5,1,3,9,13,8]这样的顺序插入,其流程是这样的:

    若按照[1,3,5,8,9,13]这样的顺序插入,其流程是这样的:

    插入的序列越接近有序,生成的二叉搜索树就越像一个链表。

    为了避免二叉搜索树变成“链表”,我们引入了平衡二叉树,即让树的结构看起来尽量“均匀”,左右子树的节点数尽量一样多。

    如何生成二叉平衡树

    先按照生成二叉搜索树的方法构造二叉树,直至二叉树变得不平衡,即出现这样的节点:左子树与右子树的高度差大于1。至于如何调整,要看插入的导致二叉树不平衡的节点的位置。主要有四种调整方式:LL(左旋)、RR(右旋)、LR(先左旋再右旋)、RL(先右旋再左旋)。

    二叉平衡树特点:左子树与右子树的高度差不大于1
    时间复杂度:log2n

    出现不平衡时到底是执行LL、RR、LR、RL中的哪一种旋转,取决于插入的位置。可以根据值的大小关系来判断插入的位置。插入到不平衡节点的右子树的右子树上,自然是要执行LL旋转;插入到不平衡节点的左子树的左子树上,自然是要执行RR旋转;插入到不平衡节点的左子树的右子树上,自然是要执行LR旋转;插入到不平衡节点的右子树的左子树上,自然是要执行RL旋转。

    经典面试算法题——判断一棵树是不是平衡二叉树(递归)
    https://leetcode-cn.com/problems/balanced-binary-tree/

    java:

    class Solution {
      private int height(TreeNode root) {
        if (root == null) {
          return -1;
        }
        return 1 + Math.max(height(root.left), height(root.right));
      }
    
      public boolean isBalanced(TreeNode root) {
        if (root == null) {
          return true;
        }
    
        return Math.abs(height(root.left) - height(root.right)) < 2
            && isBalanced(root.left)
            && isBalanced(root.right);
      }
    };
    

    相关文章

      网友评论

          本文标题:树结构-1

          本文链接:https://www.haomeiwen.com/subject/nrmedktx.html