二分搜索树(Binary Search Tree)

二分搜索树(Binary Search Tree)

一.概念及其介绍

  1. 概念
    二分搜索树(英语:Binary Search Tree),也称为 二叉查找树 、二叉搜索树 、有序二叉树或排序二叉树。满足以下几个条件:
  • 每个节点的键值大于左孩子
  • 每个节点的键值小于右孩子
  • 以左右孩子为根的子数仍然为二分搜索树
    二分搜索树
  1. 优点
    可以高效的查找数据,还可以高效的插入,删除,及动态维护数据
    二分搜索树

二分搜索树有着高效的插入、删除、查询操作。
平均时间的时间复杂度为 O(log n),最差情况为 O(n)。二分搜索树与堆不同,不一定是完全二叉树,底层不容易直接用数组表示故采用链表来实现二分搜索树。
二分搜索树

二. 操作:二分搜索树

  1. 插入操作(insert)

  2. 数据的查找(Search)

  3. 二分搜索树的包含(Contain)

  4. 二分搜索树的遍历

  5. 二分搜索树节点删除

本作品采用《CC 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!