Captain's Geek-Island Captain's Geek-Island
首页
生活如斯乎
架构师的路
  • 分类
  • 标签
  • 归档
沉洋官网 (opens new window)

SleepyOcean

走,找新大陆去
首页
生活如斯乎
架构师的路
  • 分类
  • 标签
  • 归档
沉洋官网 (opens new window)
  • 计算机基础

    • 算法与数据结构 - 总览
    • 算法与数据结构 - 链表
    • 算法与数据结构 - 树
      • 一、树
      • 二、二叉树
      • 三、二叉查找树(二叉搜索树,二叉排序树)
      • 四、平衡二叉树(AVL树)
      • 六、红黑树:
    • 算法与数据结构 - 图
    • 算法与数据结构 - 排序算法
    • 算法与数据结构 - 动态规划
    • 算法与数据结构 - 刷题集
    • 网络 - 基础
    • 网络 - TCP
    • Java - 核心知识
    • Java - 集合
    • Java - IO流
  • 并发专题

  • 性能调优专题

  • 工具专题

  • 源码框架专题

  • 设计模式

  • 分布式专题

  • 实战专题

  • 技术杂文

  • 云原生专题

  • 大数据分析专题

  • 前端专题

  • 运维专题

  • 经验专题

  • 面试专题

  • 软实力专题

  • 架构师的路
  • 计算机基础
SleepyOcean
2020-01-30

算法与数据结构 - 树

树,有二叉树、二叉查找树、平衡树、平衡二叉树、红黑树等等。本文分别罗列每种树的原理及使用案例,深入了解『树』这一数据结构

# 一、树

  1. 定义

    树(树状图)是一种数据结构 (opens new window),它是由n(n>=1)个有限结点组成一个具有层次关系的集合 (opens new window)。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。

  2. 特点:

    1. 每个结点有零个或多个子结点;
    2. 没有父结点的结点称为根结点;
    3. 每一个非根结点有且只有一个父结点;
    4. 除了根结点外,每个子结点可以分为多个不相交的子树;

树的示意图

# 二、二叉树

  1. 定义

    二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒。二叉树的第i层至多有2i-1个结点;深度为k的二叉树至多有2k-1个结点;对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

  2. 满二叉树和完全二叉树

    • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点。
    • 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~(h-1)层) 的结点数都达到最大个数,第h层所有的结点都连续集中在最左边,这就是完全二叉树。

满二叉树和完全二叉树示意图

# 三、二叉查找树(二叉搜索树,二叉排序树)

  1. 定义

    二叉查找树又称为是二叉排序树(Binary Sort Tree)或二叉搜索树。二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:

    1) 若左子树不空,则左子树上所有结点的值均小于它的根结点的值;

    2) 若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;

    3) 左、右子树也分别为二叉排序树;

    4) 没有键值相等的节点。

  2. 性质

    对二叉查找树进行中序遍历,即可得到有序的数列。它和二分查找一样,插入和查找的时间复杂度均为O(logn),但是在最坏的情况下仍然会有O(n)的时间复杂度。原因在于插入和删除元素的时候,树没有保持平衡。二叉查找树的高度决定了二叉查找树的查找效率。

# 四、平衡二叉树(AVL树)

  1. 定义

    平衡二叉树(Balanced Binary Tree)又被称为AVL树(有别于AVL算法),且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。平衡二叉树的常用算法有红黑树、AVL树等。在平衡二叉搜索树中,我们可以看到,其高度一般都良好地维持在O(log2n),大大降低了操作的时间复杂度。

    最小二叉平衡树的节点的公式如下:

    • F(n)=F(n-1)+F(n-2)+1

    这个类似于一个递归的数列,可以参考Fibonacci数列,1是根节点,F(n-1)是左子树的节点数量,F(n-2)是右子树的节点数量。

    img

    img

  2. AVL树

# 六、红黑树:

  • 变换操作:

    1. 变色: 黑 -> 红, 红 -> 黑
    2. 左旋: 这里写图片描述
    3. 右旋: 这里写图片描述
  • 变换规则: 旋转和颜色变化规则: 所有插入点默认为红色

    1. 变颜色的情况:当前结点的父亲是红色,且它的祖父结点的另一个子结点(即叔叔结点)也是红色:
      1. 把父结点设为黑色;
      2. 把叔叔结点也设为黑色;
      3. 把祖父结点设为红色;
      4. 把当前要操作的指针定义到祖父结点;
      5. 分析祖父结点变换规则;
    2. 左旋: 当前父结点是红色,叔叔是黑色,且当前结点是右子树时,以父结点为根进行左旋
    3. 右旋: 当前父结点是红色,叔叔是黑色,且当前结点是左子树时:
      1. 把父结点变为黑色;
      2. 把祖父结点变为红色;
      3. 以祖父结点作为根进行右旋;
#数据结构 #树
上次更新: 2021/03/25, 04:03:00

← 算法与数据结构 - 链表 算法与数据结构 - 图 →

新鲜出炉
01
记录 - 快速搭建自动化部署平台
04-13
02
Docker搭建各类Paas服务
03-01
03
系统配置 - Android TV配置
02-12
更多文章>
Copyright © 2019-2022 SleepyOcean | MIT License
  • 跟随系统
  • 浅色模式
  • 深色模式
  • 阅读模式