7.3树形查找

7.3树形查找

2025/9/20 13:47:58 来源：https://blog.csdn.net/2301_78200937/article/details/142638338 浏览: 次关键词：7.3树形查找

7.3.1二叉排序树

1.定义

目的:提供查找删除,插入关键字的速度

二叉排序树的特性:

左子树<根节点<右子树
左右字数也分别是一棵二叉树

对二叉排序树进行中序遍历,可以得到一个递增的有序序列

2.二叉排序树的查找

查找从根节点开始,沿分支逐层向下比较的过程

二叉排序树非空则定值与根节点数据比较
小于,则在左子树上查找,循环1,2,3
大于,则在右子树上查找,循环1,2,3

/*二叉排序树的查找*/
BST* BST_Search(BiTree T,ElemType key) {while (T!=Null&&key!=T->data) {//若数空或等于其根节点的值,则结束循环if (key < T->data) T = T->lchild;//若key小于当前值则在左子树上查找else  T = T->rchild;	//若key大于当前值则在右子树上查找}return T;
}

3.二叉排序树的插入

插入节点过程:

二叉树为空直接插入
若关键字k<根节点值,则插入到左子树
若关键字k>根节点值,则插入到右子树
若关键字k=根节点值,则插入失败,二叉排序树不允许两个相同的值存在

最坏时间复杂度o(h)

/*二叉树的插入*/
int BST_Insert(BiTree &T,KeyType k){if (T==NULL){T = (BiTree)malloc(sizeof(BSTNode));//创建新节点T->data = k;T->lchild = T->rchild = NULL;return 1;}else if (k==T->data) {//树中已有此数return 0;//插入失败}else if(k< T->data)//key<T->data,则进入左子树{BST_Insert(T.lchild,k);}else {BST_Insert(T.rchild,k);}}

4.二叉排序树的删除

1.删除叶子节点---nobody cares

2.删除node只有左子树和右子树

3.删除节点既有左子树,又有右子树

法一:找到被删除节点的直接后继

法二:找到被删除节点的直接前驱

5.二叉排序树的查找效率分析

主要取决于树的高度

最好情况二叉排序树左右子树高度差不超过1,则时间复杂度为log2n

最坏情况二叉排序树只有一个左子树or右子树,则时间复杂度为n

7.3.2平衡二叉树

1.定义

任意节点左子树右子树之差不超过1的树为平衡二叉树

出现是为了预防二叉排序树高度增长过快

平衡因子=左子树高度-右子树高度={-1,0,1}

2.平衡二叉树的插入及"不平衡"问题

1.保证"左<中<右"

2.保证平衡

3.最小不平衡字数:插入路径上离插入节点最近的平衡因子的绝对值大于1的节点作为根的子树

平衡二叉树的插入及调整操作

LL	右单旋转	将父节点右旋代替爷节点作为根节点,爷节点为父节点的右孩子
RR	左单旋转	将父节点左旋代替爷节点作为根节点,爷节点作为父节点的左孩子
LR	先左上旋,再右上旋	...
RL	先右上旋,再左上旋	......