给大家转载一篇关于红黑数的文章,感觉写的还不错。
2017年,小灰曾经发布过一篇关于红黑树的漫画,当时由于时间仓促,部分知识点一带而过,并没有讲解得很细致全面。
最近,小灰把这个知识点重新做了总结,分成上下两篇,希望大家把红黑树这个重要的数据结构彻底吃透。
————— 第二天 —————
————————————
二叉查找树(BST)具备什么特性呢?
1.左子树上所有结点的值均小于或等于它的根结点的值。
2.右子树上所有结点的值均大于或等于它的根结点的值。
3.左、右子树也分别为二叉排序树。
下图中这棵树,就是一颗典型的二叉查找树:
1.查看根结点9:
2.根据二叉查找树左子树小、右子树大的特性,10 > 9,因此值为10的结点只可能在根结点的右子树当中,我们查看右孩子结点13:
3.由于10 < 13,因此查看左孩子11:
4.由于10 < 11,因此查看左孩子10,发现10正是要查找的结点:
假设初始的二叉查找树只有三个结点,根结点值为9,左孩子值为8,右孩子值为12: