什么是树

上一篇文章已经介绍过了数组和链表,下面我们看看两者查找和操作的时间开销

可以看到,已有的数据结构不能很好的平衡静态操作和动态操作的时间开销。所以引入了树的概念

二叉排序树(也叫二叉搜索树,BST,Binary Search Tree)

大于根节点的放在根节点的右子树上,小于根节点的放在根节点的左子树上(如果等于根节点,则可视情况而定)。

如果写程序的话,可以采用递归的方式,而且由于不存在重叠子问题的情况,因此递归的性能已经足够好(不考虑栈溢出的情况)。

二叉排序树在通常情况下可以达到O(lgN)的静态、动态操作的时间复杂度。

时间复杂度 O(1)

存在一种特殊情况,即输入的数据本身就是有序的,这时二叉排序树退化成数组。

平衡二叉树(Self-balancing binary search tree)(AVL)

为了消除二叉排序树对于输入敏感的特性,引入平衡二叉树

保证每个节点左子树和右子树的高度差小于等于1就可以了

左子树深度 - 右子树深度 = 平衡因子(小于等于1)

B树&B+树

b树(balance tree)和b+树应用在数据库索引

数据库索引是存储在磁盘上的,当数据量大时,就不能把整个索引全部加载到内存了,只能逐一加载每一个磁盘页(对应索引树的节点)。所以我们要减少IO次数,对于树来说,IO次数就是树的高度,而“矮胖”就是b树的特征之一,它的每个节点最多包含m个孩子,m称为b树的阶,m的大小取决于磁盘页的大小。

b+树,是b树的一种变体,查询性能更好。有n棵子树的非叶子结点中含有n个关键字(b树是n-1个),这些关键字不保存数据,只用来索引,所有数据都保存在叶子节点(b树是每个关键字都保存数据)

红黑树(R-B Tree)

红黑树可以看做是二叉搜索树和AVL树的一个折中,可以尽量维持树的平衡,又不用话过多的时间来维持数据结构的性质。

每个结点要么是红的要么是黑的。

根结点是黑的。

每个叶结点(叶结点即指树尾端NIL指针或NULL结点)都是黑的。

如果一个结点是红的,那么它的两个儿子都是黑的。

对于任意结点而言,其到叶结点树尾端NIL指针的每条路径都包含相同数目的黑结点。

应用

广泛用在C++的STL中。map和set都是用红黑树实现的。

著名的linux进程调度Completely Fair Scheduler,用红黑树管理进程控制块。

epoll在内核中的实现,用红黑树管理事件块

nginx中,用红黑树管理timer等

Java的TreeMap实现

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181130G08CLK00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

同媒体快讯

扫码关注云+社区

领取腾讯云代金券