数据结构 -- Tree

2015-11-17 Tuesday     program

抽象地说,基本上有序列的地方就可以应用树,因为树结构即是一种序列索引结构,这里简单介绍常见的树结构。

简介

二叉树 (Binary tree) 每个节点最多只有两个分支的树结构,其分支通常被称为 “左子树” 和 “右子树” 。二叉搜索树 (Binary Search Tree) 是二叉树的一种,对于所有节点,其左子树的值小于根结点的值,右子树的值大于根结点的值。

查找、插入和删除的效率与数的高度 log n 相关,最坏可能达到 O(n) ,如下是其最坏情况,几乎达到了线性查找。

tree

为了保证树的高度,也就出现了如下的平衡二叉树,例如 AVL Tree、Red-Black Tree。

AVL Tree

自平衡二叉查找树 (AVL Tree) 中任意节点的两个子树的高度差最大为 1,查找、插入和删除在平均和最坏情况下都是 O(log n),插入和删除可能需要通过一次或多次树旋转来重新平衡这个树。这种二叉树得名于其发明者 G.M. Adelson-Velsky 和 E.M. Landis 在 1962 年的论文《An algorithm for the organization of information》。

avl tree example

一般每个节点会保存一个平衡因子 (Balance Factor) 或者通过子树高度计算,一般是左子树的高度减去它的右子树的高度,平衡因子为 1、0 或 -1 的节点被认为是平衡的,而 -2、2 的节点被认为是不平衡的,并需要重新平衡这个树。

为了保持平衡,AVL Tree 可能需要执行四种的旋转方式:

avl tree example

Red-Black Tree

Red-Black Tree 和 AVL Tree 是常用的平衡二叉搜索树,可以保证插入、查找、删除操作的最坏情况都是 O(log n)



如果喜欢这里的文章,而且又不差钱的话,欢迎打赏个早餐 ^_^


About This Blog

Recent Posts

Categories

Related Links

  • RTEMS
    RTEMS
  • GNU
  • Linux Kernel
  • Arduino

Search


This Site was built by Jin Yang, generated with Jekyll, and hosted on GitHub Pages
©2013-2019 – Jin Yang