Shulou(Shulou.com)06/01 Report--

Editor to share with you the Java binary search tree to add, insert, delete, create an example analysis, I hope you will learn something after reading this article, let's discuss it together!

① concept

Binary search tree, also known as binary sort tree, is either an empty tree or a binary tree with the following properties:

If its left subtree is not empty, then the value of all nodes on the left subtree is less than the value of the root node.

If its right subtree is not empty, the value of all nodes on the right subtree is greater than the value of the root node.

Its left and right subtrees are also binary search trees, respectively.

② Action-find

The search of binary search tree is similar to dichotomy search.

Public Node search (int key) {Node cur = root; while (cur! = null) {if (cur.val = = key) {return cur;} else if (cur.val)

< key) { cur = cur.right; }else { cur = cur.left; } } return null; }③操作-插入 public boolean insert(int key) { Node node = new Node(key); if(root == null) { root = node; return true; } Node cur = root; Node parent = null; while(cur != null) { if(cur.val == key) { return false; }else if(cur.val < key) { parent = cur; cur = cur.right; }else { parent = cur; cur = cur.left; } } //parent if(parent.val >

Key) {parent.left = node;} else {parent.right = node;} return true;} ④ Action-Delete

The delete operation is more complicated, but it is easy to understand its principle.

Set the node to be deleted as cur and the parent node to be deleted as parent

1. Cur.left = = null

1. If cur is root, then root = cur.right

2. Cur is not root,cur but parent.left, then parent.left = cur.right

3. Cur is not root,cur but parent.right, then parent.right = cur.right

2. Cur.right = = null

1. If cur is root, then root = cur.left

2. Cur is not root,cur but parent.left, then parent.left = cur.left

3. Cur is not root,cur but parent.right, then parent.right = cur.left

The second case is the same as the first case, but in the opposite direction, there is no longer drawing.

3. Cur.left! = null & & cur.right! = null

Need to use the replacement method to delete, that is, in its right subtree to find the first node in the middle order (the minimum key), fill it into the deleted node with its value, and then deal with the deletion of the node.

When we delete when the left and right subtrees are not empty, deleting the node will destroy the structure of the tree, so the scapegoat method is used to solve the problem. The actual deletion process is still in the above two cases. The nature of searching binary tree is still used here.

Public void remove (Node parent,Node 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;} else if (cur = = parent.left) {parent.left = cur.left;} else {parent.right = cur.left }} else {Node targetParent = cur; Node target = cur.right; while (target.left! = null) {targetParent = target; target = target.left;} cur.val = target.val If (target = = targetParent.left) {targetParent.left = target.right;} else {targetParent.right = target.right;}} public void removeKey (int key) {if (root = = null) {return;} Node cur = root; Node parent = null While (cur! = null) {if (cur.val = = key) {remove (parent,cur); return;} else if (cur.val

< key){ parent = cur; cur = cur.right; }else { parent = cur; cur = cur.left; } } }⑤性能分析 插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。 对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度 的函数，即结点越深，则比较次数越多。 但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树： 最优情况下，二叉搜索树为完全二叉树，其平均比较次数为：

In the worst case, the binary search tree degenerates to a single-branch tree, and the average number of comparisons is:

⑥ complete code public class TextDemo {public static class Node {public int val; public Node left; public Node right; public Node (int val) {this.val = val;}} public Node root; / * find * @ param key * / public Node search (int key) {Node cur = root While (cur! = null) {if (cur.val = = key) {return cur;} else if (cur.val)

< key) { cur = cur.right; }else { cur = cur.left; } } return null; } /** * * @param key * @return */ public boolean insert(int key) { Node node = new Node(key); if(root == null) { root = node; return true; } Node cur = root; Node parent = null; while(cur != null) { if(cur.val == key) { return false; }else if(cur.val < key) { parent = cur; cur = cur.right; }else { parent = cur; cur = cur.left; } } //parent if(parent.val >

Key) {parent.left = node;} else {parent.right = node;} return true;} public void remove (Node parent,Node 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 } else if (cur = = parent.left) {parent.left = cur.left;} else {parent.right = cur.left;}} else {Node targetParent = cur; Node target = cur.right; while (target.left! = null) {targetParent = target Target = target.left;} cur.val = target.val; if (target = = targetParent.left) {targetParent.left = target.right;} else {targetParent.right = target.right }} public void removeKey (int key) {if (root = = null) {return;} Node cur = root; Node parent = null; while (cur! = null) {if (cur.val = = key) {remove (parent,cur); return } else if (cur.val < key) {parent = cur; cur = cur.right;} else {parent = cur; cur = cur.left After reading this article, I believe you have a certain understanding of "sample Analysis of adding, inserting, deleting and creating Java binary search Tree". If you want to know more about it, welcome to follow the industry information channel, thank you for reading!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.