Binary search tree ( Binary sort tree )

<> one . concept

Binary search tree is also called binary sort tree , Has the following properties ：

* If its left subtree is not empty , Then the values of all nodes on the left subtree are less than the values of the root node
* If its right subtree is not empty , Then the values of all nodes on the right subtree are greater than the values of the root node
* Its left and right subtrees are also binary search trees
be careful ： The results of order traversal in binary search tree are ordered

<> two , basic operation

<>1. Find elements

thinking ： The left subtree of a binary search tree is always smaller than the root node , And its right subtree is larger than the root node . If the current node is larger than the one you are looking for, go to the left , If the current element is smaller than the one you are looking for, go to the right
public Node search(int key) { if(root == null) { return null; } Node cur = root
; while (cur != null) { if(cur.val == key) { return cur; }else if(cur.val > key)
{ cur = cur.left; }else{ cur = cur.right; } } return null; }
<>2. Insert element

If it is an empty tree, insert the element directly root The position is good
thinking ： Because it is a binary search tree, duplicate elements cannot be inserted , And each insertion is at the position of the leaf node . Define a cur
from root start , If the inserted element is smaller than the current position element, go to the left , Go right if it is larger than the current position element , Until empty , So you need to define another variable parent remember cur Position in front of .
Finally, determine whether to insert into parent Left subtree or right subtree position of

code implementation ：
public boolean insert(int key) { Node node = new Node(key); if(root == null) {
this.root = node; return true; } Node parent = null; Node cur = root; while (cur
!= null) { if(cur.val == key) { // Have the same elements directly return return false; }else if(cur.val
> key) { parent = cur; cur = cur.left; }else{ parent = cur; cur = cur.right; } }
if (parent.val > key) { parent.left = node; }else{ parent.right = node; } return
true; }
<>3. Delete element

Deleting elements is a difficult point , There are many situations to consider

*
cur.left == null

* cur yes root, be root = cur.right
* cur no root,cur yes parent.left, be parent.left = cur.right
* cur no root,cur yes parent.right, be parent.right = cur.right
*
cur.right == null

* cur yes root, be root = cur.left
* cur no root,cur yes parent.left, be parent.left = cur.left
* cur no root,cur yes parent.right, be parent.right = cur.left
*
cur.left != null && cur.right != null
Delete by scapegoat

* Locate the node to delete , The leftmost node of the right tree or find the rightmost node of the left tree , Replace the val value .
* So that we can ensure , The left tree must be smaller than the root node after deletion , The right tree must be larger than the root node
public boolean remove(int key) { if(this.root == null) { return false; } Node
parent= null; Node cur = this.root; while (cur != null) { if(cur.val == key) {
removeKey(parent,cur); return true; }else if(cur.val < key) { parent = cur; cur
= cur.right; }else{ parent = cur; cur = cur.left; } } return false; } public
void removeKey(Node parent,Node cur) { if(cur.left == null) { if(cur == this.
root) { this.root = this.root.right; }else if(cur == parent.left) { parent.left
= cur.right; }else{ parent.right = cur.right; } }else if(cur.right == null) { if
(this.root == cur) { this.root = this.root.left; }else if(cur == parent.left) {
parent.left = cur.left; }else{ parent.right = cur.left; } }else{// Left and right are not empty Node
targetParent= cur; Node target = cur.right; while (target.left != null) {
targetParent= target; target = target.left; } cur.val = target.val; if(
targetParent.left == target) { targetParent.left = target.right; }else{
targetParent.right = target.right; } } }
<>4. performance analysis

Both insert and delete operations must first find , The search efficiency represents the performance of each operation in the binary search tree
Yes n Binary search tree with nodes , If the probability of finding each element is equal , Then the average search length of the binary search tree is a function of the depth of the node in the binary search tree , That is, the deeper the node is , The more comparisons .
But for the same key set , If keys are inserted in different order , Possible binary search trees with different structures ：

Best case scenario ： Binary search tree is a complete binary tree , The average number of comparisons is O(log 2 _2 2​n)

Worst case scenario ： Binary search tree degenerates into a single branch tree , The average number of comparisons is ：O

<> All codes ：
public class BinarySearchTree { public static class Node { int val; Node left;
Node right; public Node(int val) { this.val = val; } } public Node root = null;
/** * Find a node * @param key */ public Node search(int key) { if(root == null) {
return null; } Node cur = root; while (cur != null) { if(cur.val == key) {
return cur; }else if(cur.val > key) { cur = cur.left; }else{ cur = cur.right; }
} return null; } /** * Insert element * @param key * @return */ public boolean insert(int
key) { Node node = new Node(key); if(root == null) { this.root = node; return
true; } Node parent = null; Node cur = root; while (cur != null) { if(cur.val ==
key) { // Have the same elements directly return return false; }else if(cur.val > key) { parent = cur;
cur= cur.left; }else{ parent = cur; cur = cur.right; } } if (parent.val > key) {
parent.left = node; }else{ parent.right = node; } return true; } /** * Delete element *
@param key */ public boolean remove(int key) { if(this.root == null) { return
false; } Node parent = null; Node cur = this.root; while (cur != null) { if(cur.
val== key) { removeKey(parent,cur); return true; }else if(cur.val < key) {
parent= cur; cur = cur.right; }else{ parent = cur; cur = cur.left; } } return
false; } public void removeKey(Node parent,Node cur) { if(cur.left == null) { if
(cur == this.root) { this.root = this.root.right; }else if(cur == parent.left) {
parent.left = cur.right; }else{ parent.right = cur.right; } }else if(cur.right
== null) { if(this.root == cur) { this.root = this.root.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(
targetParent.left == target) { targetParent.left = target.right; }else{
targetParent.right = target.right; } } } }

• « 上一篇：MyBatis-plus of IPage paging
• » 下一篇：“Python Is the best language in the world ”