又叫二叉查找树,二叉排序树,它具有以下特点
1.如果它的左子树不为空,则左子树上节点的值都小于根节点
2.右子树不为空,则右子树上的值都大于根节点
3.子树同样遵循以上两点
为什么又叫二叉排序树呢？二叉树的变量方式:前 中 后 层次
只要一棵树是二叉搜索树,那么他的中序遍历一定是有序的
1.和根节点比较大小,小放在左侧,大就放在右侧
2.如果没有左或右就直接放，如果右继续递归比较
时间复杂度 O(nlogn)
1.先和根节点比较,小的在左侧找,大的在右侧找
2.继续递归
时间复杂度 O(logn)
时间复杂度 O(logn) 复杂的那种
性质
1.每个节点不是红就是黑
2.不可能有连在一起的红色节点，每个叶子节点都是黑色的空节点NIL，也就是说叶子节点不存储数据
3.根节点都是黑色的root
4.每个节点，从该节点到其他可达叶子节点的所有路径，都包含相同数目的黑色节点
为了满足以上的性质 就出现了旋转
1、什么是红黑树？ 红黑树是一个要求不那么严格的平衡二叉树搜索树（平衡二叉搜索树/AVL树=平衡二叉树+二叉搜索树...
彻底理解红黑树（一）之二叉搜索树彻底理解红黑树（二）之插入彻底理解红黑树（三）之删除 1. 二叉搜索树的定义 二叉...
二叉搜索树和红黑树
一、map map内部实现了一个红黑树（红黑树是非严格平衡二叉搜索树，而AVL是严格平衡二叉搜索树），红黑树具有自...
二叉搜索树, 平衡二叉树(AVL) 红黑树 B树(平衡多路搜索树) B+树(在B树上改造) 二叉搜索树...
一、红黑树（Red Black Tree） 1、初识红黑树 红黑树也是一种自平衡的二叉搜索树，也曾叫做平衡二叉B树...
彻底理解红黑树（一）之 二叉搜索树彻底理解红黑树（二）之 插入彻底理解红黑树（三）之 删除 前言 红黑树的插入情况...
彻底理解红黑树（一）之 二叉搜索树彻底理解红黑树（二）之 插入彻底理解红黑树（三）之 删除 前言 红黑树的删除情况...
红黑树 红黑树也是一种自平衡的二叉搜索树以前也叫做平衡二叉B树(Symmetric Binary B-tree) ...
红黑树(Red Black Tree) ◼ 红黑树也是一种自平衡的二叉搜索树以前也叫做平衡二叉B树(Symmetr...
本文标题：二叉搜索树、红黑树
本文链接：https://www.haomeiwen.com/subject/mxuoartx.html
网友评论