二叉查找树

二叉查找树(Binary Search Tree),也称为二叉搜索树,是具有下列性质的二叉树

1.若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值

2.若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值

3.任意节点的左、右子树也分别为二叉查找树

4.没有键值相等的节点。

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低


最坏情况:

加入所有的节点都在树的一边,组成了链表,那么查找时间复杂度变为线性,为 O(n),比如

  1
   \
    3
     \
      4
       \
        8
         \
          9
           \
            10

最好情况:

即为平衡二叉树,时间复杂度为 O(logn)

            8
         /     \
        3       10
       / \     /
      1   4   9

发明平衡二叉查找树这类数据结构的初衷是,解决普通二叉查找树在频繁的插入、删除等动态更新的情况下,出现时间复杂度退化的问题

所以,平衡二叉查找树中“平衡”的意思,其实就是让整棵树左右看起来比较“对称”、比较“平衡”,不要出现左子树很高、右子树很矮的情况。这样就能让整棵树的高度相对来说低一些,相应的插入、删除、查找等操作的效率高一些



上一篇: 
下一篇: AVL树
作者邮箱: 203328517@qq.com