图解:二叉搜索树算法

“岁月极美,在于它必然的流逝”

“春花 秋月 夏日 冬雪”
— 三毛

一、树 & 二叉树

是由节点和边构成,储存元素的集合。节点分根节点、父节点和子节点的概念。
如图:树深=4; 5是根节点;同样8与3的关系是父子节点关系。

1

二叉树binary tree,则加了“二叉”(binary),意思是在树中作区分。每个节点至多有两个子(child),left child & right child。二叉树在很多例子中使用,比如二叉树表示算术表达式。
如图:1/8是左节点;2/3是右节点;

2_2

二、二叉搜索树 BST

顾名思义,二叉树上又加了个搜索的限制。其要求:每个节点比其左子树元素大,比其右子树元素小。
如图:每个节点比它左子树的任意节点大,而且比它右子树的任意节点小

2_3

三、BST Java实现

直接上代码,对应代码分享在 Github 主页
BinarySearchTree.java

1. 节点数据结构
首先定义了节点的数据接口,节点分左节点和右节点及本身节点值。如图

2_4

代码如下:

2. 插入
插入,和删除一样会引起二叉搜索树的动态变化。插入相对删处理逻辑相对简单些。如图插入的逻辑:

2_5
a. 从root节点开始
b.如果root为空,root为插入值
c.循环:
d.如果当前节点值大于插入值,找左节点
e.如果当前节点值小于插入值,找右节点
代码对应:

3.查找

其算法复杂度 : O(lgN),树深(N)。如图查找逻辑:

2_6
a.从root节点开始
b.比当前节点值小,则找其左节点
c.比当前节点值大,则找其右节点
d.与当前节点值相等,查找到返回TRUE
e.查找完毕未找到
代码对应:

4. 删除
首先找到删除节点,其寻找方法:删除节点的后继者是在其右节点树种最小的节点。如图删除对应逻辑:2_7

结果为:

2_8
a.找到删除节点
b.如果删除节点左节点为空 , 右节点也为空;
c.如果删除节点只有一个子节点 右节点 或者 左节点
d.如果删除节点左右子节点都不为空
代码对应见上面完整代码。

案例测试代码如下,BinarySearchTreeTest.java

运行结果如下:

四、小结

与偶尔吃一碗“老坛酸菜牛肉面”一样的味道,品味一个算法,比如BST,的时候,总是那种说不出的味道。

树,二叉树的概念

BST算法

相关代码分享在 Github 主页

1 7 收藏 评论

相关文章

可能感兴趣的话题



直接登录
跳到底部
返回顶部