数据结构之二叉查找树和红黑树
分类:
文章
•
2022-11-07 09:36:47
二叉查找树和红黑树
-
首先我们搞清楚什么是数据结构
-
Clifford A.Shaffer在《数据结构与算法分析》一书中的定义是
数据结构是 ADT(抽象数据类型Abstract Data Type) 的物理实现。
-
白话文
是相互之间存在一种或多种特定关系的数据元素的集合`
二叉查找树
-
什么是二叉查找树
-
对于二叉树中的每个节点X,它的左子树中所有项的值都小于
X中的项,它的右子树中所有项的值大于
X中的项。这样的二叉树是二叉查找树。
-
特点
当前节点的左子节点都是小于当前节点的(前提是左子节点不为空
);
当前节点的右子节点都是大于当前节点(前提是右子节点不为空
);
其他的左右子树也分别为二叉查找树;
-
缺点
-
前提
假设初始的二叉查找树只有三个节点,根节点值为9,左孩子值为8,右孩子值为12:
-
-
当我们再连续的插入连续的递减的key(7,6,5,4,3)时,我们的二叉树就成一下这个样子
so,我们可以直接看到这样的二叉树变得非常的不平衡,这也就延伸到了我们的红黑树
红黑树
-
什么是红黑树
-
怎么达到自平衡???
-
红黑树的特征
节点是红色或者是黑色
根节点是黑色
每个叶子节点都是黑的空节点(NIL)
-
每个红色节点的子节点都是黑色的
从任何一节点到其节点的叶子节点的黑色节点的数量都是相同的
-
红黑树节点称呼
下一章写红黑树的插入删除和查找流程—–>