什么是二叉查找树呢?
二叉查找树(BST)具备以下特性:
- 左子树上所有结点的值均小于或等于它的根结点的值。
- 右子树上所有结点的值均大于或等于它的根结点的值。
- 左、右子树也分别为二叉排序树。
二叉搜索树 BST的完美情况
一般人们理解的二叉树(又叫二叉搜索树 BST)会出现一个问题,完美的情况下,它是这样的:
二叉搜索树的查找流程
如何查找值为7的节点?
1.查看根节点8,因为7<8,所以再查看它的左子节点6
2.查看左子节点6,因为7>6,所以再查看它的右子节点7
3.查看右子节点7,因为7=7,所以就找到啦,
二叉搜索树的极端情况
二叉查找树是有缺点的,在不断插入的时候,有可能出现这样一种情况:很容易“退化”成链表,
如果bst 树的节点正好从大到小的插入,此时树的结构也类似于链表结构,这时候的查询或写入耗时与链表相同。
退化成为了 链表的特殊BST
一颗特殊BST,退化成为了 链表,如下图:
它和链表一样,搜索的时候,最坏情况的时间复杂度O(n) 。
那么我们怎么避免这种情况呢?
为了避免这种特殊的情况发生,引入了平衡二叉树(AVL)和红黑树(red-black tree)。
AVL 、rbt 都是通过本身的建树原则来控制树的层数和节点位置,
因为rbtree是由AVL演变而来,所以我们从了解AVL开始。
© 版权声明
本站文章由不念博客原创,未经允许严禁转载!
THE END