二叉搜索树简单介绍

自我介绍：初次电话交流，先简单介绍自己。 #生活技巧# #沟通技巧# #电话沟通技巧#

目录 二叉搜索树1. 概述2. 查询二叉搜索树1. 查找1. 查找伪代码 2. 最大关键字元素和最小关键字元素1. 最小关键字元素2. 最小关键字元素伪代码3. 最大关键字元素伪代码4. 后继和前驱5. 后继伪代码 2. 插入和删除1. 插入1. 插入伪代码 2. 删除1. 移动伪代码2. 删除伪代码 二叉搜索树 1. 概述

一棵二叉搜索树是以一棵二叉树组织的，其中每个结点就是一个对象，每个节点包含属性left、right、p，它们分别指向结点的左孩子，右孩子和双亲，如果某个结点的孩子的属性值不在，则为NIL。对任何结点x，x左子树中的关键字最大不超过x.key，右子树中的关键字最小不低于x.key。
二叉搜索树上基本操作所花费的时间与这棵树的高度成正比。对于有n个节点的完全二叉树来说，操作的最坏运行时间为Θ(lgn),如果这棵树是一条n个节点组成的线性链，操作的最坏运行时间为Θ(n)

2. 查询二叉搜索树 1. 查找

通过输入一个指向树根的指针和一个关键字k查找结点，如果结点存在，返回一个指向关键字为k的节点的指针

1. 查找伪代码

ITERATIVE-TREE-SEARCH(x, k) while x ≠ NIL and k ≠ x.key if(k < x.key) x = x.left else x = x.right return x 123456 2. 最大关键字元素和最小关键字元素 1. 最小关键字元素

通过树根沿着left孩子指针直到遇到一个NIL,返回一个指向在已给定结点x为根的子树中的最小元素的指针。假设不为NIL

2. 最小关键字元素伪代码

TREE-MINIMUM(x) while x.left ≠ NIL x = x.left return x 1234 3. 最大关键字元素伪代码

TREE-MAXIMUM(x) while x.right ≠ NIL x = x.right return x 1234 4. 后继和前驱

如果一个二叉树所有的关键字都不相同，则一个结点x的后继是大于x.key的最小关键字的结点。

5. 后继伪代码

TREE-SUCCESSOR(x) if x.right ≠ NIL return TREE-MINIMUM(x.right) y = x.p while y ≠ NIL and x == y.rightx = yy = y.p retrun y 12345678

在一个高度为h的我二叉搜索树上，上面几种的动态集合上的操作可以在O(h)时间内完成

2. 插入和删除 1. 插入 1. 插入伪代码

TREE-INSERT(T, z)y = NILx = T.rootwhile x ≠ NILy = xif z.key < x.keyx = x.leftelse x = x.rightz.p = yif y == NILT.root = zelseif z.key < y.keyy.left = zelse y.right = z 1234567891011121314 2. 删除

删除会有以下四种情况：

结点z没有左孩子，用右孩子r来替换z，其中r可以使NIL，也可以不是结点z有一个左孩子h，但没有右孩子，用h来替换z结点z有两个孩子，其左孩子是结点h，右孩子r还是其后继，r的右孩子是结点x，用r替换z，修改h成为r的左孩子，但保留x仍为r的右孩子，结点z有左孩子h和右孩子r且为q的孩子，并且z的后继y ≠ r 位于以r为根的子树中，用y自己的右孩子来代替y，并且置y为r的双亲，然后再置y为q的孩子和h的双亲 1. 移动伪代码

TRANSPLANT(T, u, v)if u.p == NILT.root = velseif u == u.p.leftu.p.left = velse u.p.right = vif v ≠ NILv.p = u.p 12345678 2. 删除伪代码

TREE-DELETE(T, z)if z.left = NILTRANSPLANT(T, z, z.right)elseif z.right == NILTRANSPLANT(T, z, z.left) else y = TREE-MINIMUM(z.right)if y.p ≠ zTRANSPLANT(T, y, y.right)y.right = z.righty.right.p = yTRANSPLANT(T,z,y)y.left = z.lefty.left.p = y 12345678910111213

在一棵高度为h的二叉搜索树上，实现动态插入和删除的运行时间均为O(h)

网址：二叉搜索树简单介绍 https://www.yuejiaxmz.com/news/view/443422

相关内容

最优二叉检索树
二叉树非递归遍历
题解：二叉树问题
环保材质材料的简单介绍
简单的艺术生自我介绍
扫地清扫车简单介绍，功能特点分析！
简单的生活介绍
【简单美容方法介绍】
搜狗图片搜索
二手房简单翻新攻略的具体内容介绍

随便看看