本文主要是介绍【数据结构】详解二叉搜索树及其实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言:
二叉搜索树是红黑树等的前身,掌握其操作和性质很重要。总结自用and分享。
目录
一、基本概念
二、其常见操作及其实现
1.定义节点
2.查找元素
3.插入元素
4.删除元素【难点】
三、性质分析
一、基本概念
如下所示:对于所有节点都满足该性质:子树上所有节点的值都小于该节点的值。对于每个节点,右子树上所有节点的值都大于该节点的值。每个节点的左子树和右子树也是一个二叉搜索树。
其也叫二叉排序树,对其进行中序遍历可以得到排好序的序列。
二、其常见操作及其实现
1.定义节点
public class BinarySearchTree {private TreeNode root = null;//根节点// 定义节点class TreeNode {int val;TreeNode left;TreeNode right;public TreeNode(int val) {this.val = val;}
}
2.查找元素
思想:
运用一个递归的思想:
1.先看看根节点是不是该元素,是的话,直接当前节点。
2.若不是,判断其位置,若该元素比根大,那就去右子树找(跳到1)。
3.若该元素比根小,那就去左子树找(跳到1)。
4.若遍历完所有节点都找不到,返回null。
代码实现:
public TreeNode search(int val) {TreeNode curRoot = root;//当前的双亲节点while (curRoot != null) {if (curRoot.val == val) {return curRoot;} else if (curRoot.val > val) {curRoot = curRoot.left;} else {curRoot = curRoot.right;}}return null;}
3.插入元素
注意:二叉树的插入是不会破坏原有的结构的,插入元素,总是能找到合适的叶子节点插入,你们可以画图感受一下。
思想:
1.若该树为空,直接插入。
2.若树不为空:根据二叉树的性质,找到它的容身之处的双亲节点。
3.找到双亲节点之后,若比双亲节点大,插入其右边,若比双亲节点小,插入其左边。
代码实现:
// 2.插入元素public boolean insert(int val) {// 如果根节点为空,直接插入,返回trueif (root == null) {root = new TreeNode(val);return true;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val == cur.val) {System.out.println("值为" + val + "的节点已经存在");return false;} else if (val > cur.val) {parent = cur;cur = cur.right;} else {parent = cur;cur = cur.left;}}// 抵达该位置时,已经找到合适的插入位置的双亲节点:parent// 要判断一下插入哪一边if (val > parent.val) {parent.right = new TreeNode(val);} else {parent.left = new TreeNode(val);}return true;}
4.删除元素【难点】
注意:刚说的插入元素不会破坏原有的树结构,但是删除元素就可能不得不破坏原有的树结构了,毕竟要把某个在中间的元素搬走...
a:初步思路:
先找到该节点和其双亲节点,若找不到该节点,返回false。若找到了该节点,再根据情况进行删除调整。
public boolean remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (cur.val < val) {parent = cur;cur = cur.right;} else if (cur.val > val) {parent = cur;cur = cur.left;} else {//找到要删除的元素和其双亲节点了removeNode(parent, cur);return true;}}System.out.println("删除失败,没找到值为"+val+"的节点");return false;}
b:删除:(难点)
- 删除叶子节点:直接删除。
- 删除只有一边子节点的节点:用子节点替代该节点。(可涵盖情况1)
- 删除有两个子节点的节点【难点所在】:找到该节点的中序后继节点,用它的值替换被删除节点的值,然后删除该中序后继节点,并把该中序后继节点的子节点继承过去。
再捋一下删除的情况:
情况1、2: 我们找到了要删除的节点和其双亲节点。上述的情况2是可以包含情况1的:叶子节点也可以视为只有一边子节点(实际是null)的节点,然后子节点(实际是null),替代原本的节点。但是有一种情况我们要特殊处理,那就是要删除的节点是根节点时(此时对parent修改,只是流动了parent,影响不了root),我们需要直接拿到root去修改指向。
情况3: 删除有两个子节点的节点【难点所在】
找到要删除节点的右子树的最左节点,我们因为是最左节点,该节点肯定没有左子树了。
我们把最左节点的值直接覆盖到要删除的节点,原因:最左节点是要删除节点的右子树里最小的,把它放在要删除的节点处,既可以满足,右子树中所有元素比节点大,也可以满足本来左子树中所有元素比节点小。(天然,右子树中任一元素大于左子树中的)
善后阶段:最左节点的值已经被拿去,应该要删掉。这时候就回到情况1、2的问题了,且最左节点肯定不是头结点,处理起来也更简单。
private void removeNode(TreeNode parent, TreeNode cur) {// 情况1:要删除的节点没有左子节点if (cur.left == null) {// 如果要删除的节点是根节点,则直接将根节点指向其右子节点if (cur == root) {root = cur.right;} else if (cur == parent.left) {// 如果要删除的节点是其父节点的左子节点,则更新父节点的左指针parent.left = cur.right;} else {// 如果要删除的节点是其父节点的右子节点,则更新父节点的右指针parent.right = cur.right;}}// 情况2:要删除的节点没有右子节点else if (cur.right == null) {// 如果要删除的节点是根节点,则直接将根节点指向其左子节点if (cur == root) {root = cur.left;} else if (cur == parent.left) {// 如果要删除的节点是其父节点的左子节点,则更新父节点的左指针parent.left = cur.left;} else {// 如果要删除的节点是其父节点的右子节点,则更新父节点的右指针parent.right = cur.left;}}// 情况3:要删除的节点有左右子节点else {// 找到要删除节点的右子树中的最左(最小)节点TreeNode t = cur.right;TreeNode tp = cur;while (t.left != null) {tp = t;t = t.left;}// 将最左节点的值赋值给要删除的节点cur.val = t.val;// 删除最左节点,更新其父节点的左指针或右指针if (tp.left == t) {tp.left = t.right;} else {tp.right = t.right;}}}
三、性质分析
由于二叉搜索树的特点,平均情况下,插入、查找和删除操作的时间复杂度都是 O(logn)。但是,如果二叉搜索树退化成一条链表(例如插入有序数据),最坏情况下,操作时间复杂度会降到 O(n)。为了避免这种情况,实际应用中常使用平衡二叉搜索树(如AVL树、红黑树等)。
这篇关于【数据结构】详解二叉搜索树及其实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!