二叉搜索树(Java实现)

博主主页: 码农派大星.

数据结构专栏:Java数据结构

数据库专栏:MySQL数据库

JavaEE专栏:JavaEE

关注博主带你了解更多数据结构知识

1.概念

2.实现二叉搜索树

定义节点

查找元素

插入元素

删除元素

1.概念

二叉搜索树又称二叉排序树,或者它是一棵空树,或者是具有以下性质的二叉树:

若它的左子树不为空，则左子树上所有节点的值都小于根节点的值

若它的右子树不为空，则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

2.实现二叉搜索树

定义节点

static class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode(int val){this.val=val;}}public TreeNode root = null;

查找元素

  //查找public TreeNode seach(int key){TreeNode cur = root;while ( cur != null){  //根节点的值不等于要查找的key值,接下来循环if (cur.val < key){//根节点的值小于key值,让其在右子树继续查找cur = cur.right;}else if(cur.val > key){//根节点的值大于key值,让其在左子树继续查找cur = cur.left;}else {//找到了key值,返回即可return cur;}}return null;//树中没有要找的key值,直接返回null}

插入元素

1.如果为空，那么直接插入
2.如果不为空，如果小于根则插入左边，大于则插入右边

 //插入public void insert(int val){TreeNode node = new TreeNode(val);if(root == null){root = node;return;}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 {return;}}if(parent.val > val){parent.left = node;}else{parent.right = node;}}

删除元素

需要使用替换法进行删除，即在它的右子树中寻找中序下的第一个结点，用它的值填补到被删除节点中

 //删除public void remove(int key) {TreeNode parent = null;TreeNode cur = root;while (cur != null) {if(cur.val < key) {parent = cur;cur = cur.right;}else if(cur.val > key) {parent = cur ;cur = cur.left;}else {removeNode(parent,cur);return;}}}private void removeNode(TreeNode parent,TreeNode cur) {if(cur.left == null) {if(cur == root) {root = cur.right;}else if(cur == parent.left) {parent.left = cur.right;}else {parent.right = cur.right;}}else if(cur.right == null) {if(cur == root) {root = cur.left;}if(cur == parent.left) {parent.left = cur.left;}else {parent.right = cur.left;}}else {//cur.left！=null&&cur.right!=null,//那么就在cur的左边找到最大值，或者cur的右边找到最小值来替换该元素TreeNode target = cur.right;TreeNode targetP = cur;while (target.left != null) {targetP = target;target = target.left;}cur.val = target.val;if(target == targetP.left) {targetP.left = target.right;}else {targetP.right = target.right;}}}

性能分析:

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
最优情况下，二叉搜索树为完全二叉树，其平均比较次数为： $log_{2}N$
最差情况下，二叉搜索树退化为单支树，其平均比较次N数为： $\frac{N}{2}$