23--数据结构简述

发布时间:2023年12月20日

常见的数据结构

数据存储的常用结构有:栈、队列、数组、链表和红黑树。

1、栈

特点:先进后出

2、队列

特点:先进先出

3、数组

数组特点:查询快 , 增删慢

整形数组:

对象数组:

4、链表

链表的特点

逻辑结构:线性结构

物理结构:不要求连续的存储空间

存储特点:链表由一系列结点node(链表中每一个元素称为结点)组成,结点可以在代码执行过程中动态创建。每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

常见的链表结构有如下的形式:

5、树

5.1 二叉树

二叉树(Binary tree)是树形结构的一个重要类型。二叉树特点是每个结点最多只能有两棵子树,且有左右之分。

二叉排序/查找/搜索树:即为BST (binary search/sort tree)。满足如下性质:

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

(2)若它的右子树上所有结点的值均大于它的根节点的值;

(3)它的左、右子树也分别为二叉排序/查找/搜索树。

5.2 平衡二叉树

平衡二叉树:(Self-balancing binary search tree,AVL)首先是二叉排序树,此外具有以下性质:

(1)它是一棵空树或它的左右两个子树的高度差的绝对值不超过1

(2)并且左右两个子树也都是一棵平衡二叉树

(3)不要求非叶节点都有两个子结点

5.3 红黑树

红黑树:即Red-Black Tree。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,它是在 1972 年由 Rudolf Bayer 发明的。红黑树是复杂的,但它的操作有着良好的最坏情况运行时间,并且在实践中是高效的:它可以在 O(log n)时间内做查找,插入和删除, 这里的 n 是树中元素的数目。

红黑树的特性:

  • 每个节点是红色或者黑色
  • 根节点是黑色
  • 每个叶子节点(NIL)是黑色。(注意:这里叶子节点,是指为空(NIL或NULL)的叶子节点)
  • 每个红色节点的两个子节点都是黑色的。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
  • 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点(确保没有一条路径会比其他路径长出2倍)

文章来源:https://blog.csdn.net/weixin_46612641/article/details/135080803
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。