二叉搜索树 Binary Search Tree

  • 结构
  • 分析
  • 红黑树(Red-Black Tree)

二叉搜索树(Binary Search Tree),又叫做二叉查找树、有序二叉树。二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势。

结构

它有两个性质:

  1. 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值,若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值。
  2. 它的左、右子树也分别二叉搜索树。

示例:

分析

二叉搜索树相关的操作有:查找、选择、最大值/最小值、找排序后的前一项/后一项、排序输出、插入、删除等。

假设一颗树有n个节点,那么它的高度可能为 [\log_2 n, n]。上述操作的时间复杂度为:

  • 查询(Search): \Theta(\log n)
  • 选择(Select): O(\log n)
  • 最大值/最小值(Max/Min): O(\log n)
  • 排序后的前一项/后一项(Predessor/Successor): O(\log n)
  • 排序输出: O(n)
  • 插入(Insert): O(\log n)
  • 删除(Delete): O(\log n)

对于查询(Search)、插入(Insert)、最大值/最小值(Max/Min)来说,最坏的情况时间复杂度为\Theta(height)

红黑树(Red-Black Tree)

进一步延伸到红黑树,红黑树是一种自平衡二叉搜索树,经常用于关联数组。红黑树有以下几个性质:

  1. 每个节点为红色或黑色。
  2. 根节点为黑色。
  3. 两个红色节点不能相邻,也就是红色节点的子节点一定为黑色。
  4. 所有叶子节点(null)都为黑色节点。
  5. 从任意一个节点到叶子节点的所有路径都包含相同数量的黑色节点。

由于红黑树是平衡二叉搜索树,它的高度至多为( \log n +1) 。红黑树相关操作有:旋转(左旋、右旋)、插入和删除等。旋转包括左旋和右旋,左旋是将x变为一个左节点,右旋是将x变为一个右节点。

参考资料

  1. 百度百科 二叉搜索树
  2. 百度百科 红黑树
  3. sky Wang 红黑树(一)之 原理和算法详细介绍

You May Also Like

About the Author: 雪球

一个在读的工科研究生 一个努力追赶时代脚步的人 Github: https://github.com/xueqiwang0v0 LinkedIn: https://www.linkedin.com/in/xueqi-wang-0939b51a6/

发表评论

邮箱地址不会被公开。 必填项已用*标注