什么是BST二叉查找树,以及查找流程详解

什么是二叉查找树呢?

二叉查找树(BST)具备以下特性:

  1. 左子树上所有结点的值均小于或等于它的根结点的值。
  2. 右子树上所有结点的值均大于或等于它的根结点的值。
  3. 左、右子树也分别为二叉排序树。

二叉搜索树 BST的完美情况

一般人们理解的二叉树(又叫二叉搜索树 BST)会出现一个问题,完美的情况下,它是这样的:

图片[1]-什么是BST二叉查找树,以及查找流程详解-不念博客
BST

二叉搜索树的查找流程

如何查找值为7的节点?
1.查看根节点8,因为7<8,所以再查看它的左子节点6
2.查看左子节点6,因为7>6,所以再查看它的右子节点7
3.查看右子节点7,因为7=7,所以就找到啦,

二叉搜索树的极端情况

二叉查找树是有缺点的,在不断插入的时候,有可能出现这样一种情况:很容易“退化”成链表,

如果bst 树的节点正好从大到小的插入,此时树的结构也类似于链表结构,这时候的查询或写入耗时与链表相同。

退化成为了 链表的特殊BST

一颗特殊BST,退化成为了 链表,如下图:

图片[2]-什么是BST二叉查找树,以及查找流程详解-不念博客
特殊BST

它和链表一样,搜索的时候,最坏情况的时间复杂度O(n) 。

那么我们怎么避免这种情况呢?

为了避免这种特殊的情况发生,引入了平衡二叉树(AVL)和红黑树(red-black tree)。

AVL 、rbt 都是通过本身的建树原则来控制树的层数和节点位置,

因为rbtree是由AVL演变而来,所以我们从了解AVL开始。

© 版权声明
THE END