13518219792
一：概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:
若它的左子树不为空，则左子树上所有节点的值都小于根节点的值
若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
它的左右子树也分别为二叉搜索树。
二：操作——查找
先和根节点做对比，相等返回，如果不相等，
关键码key>根节点key,在右子树中找(root=root.rightChild)
关键码key<根节点key,在左子树中找(root=root.leftChild)
否则返回false
三：操作——插入
根据二叉排序树的性质，左孩子比根节点的值小，右孩子比根节点的值大。关键码key先于根节点key作比较，然后再判断与根节点的左或者右作比较，满足二叉排序树性质时，即为合理位置，然后插入。
四： 操作-删除（难点）
设待删除结点为 cur, 待删除结点的双亲结点为 parent
1. cur.left == null
五：实现
public class BinarySearchTree, V>
{
public static class Node, V>
{
K key;
V value;
Node left;
Node right;
public String toString()
{
return String.format("{%s, %s}", key, value);
}
}
private Node root = null;
public V get(K key)
{
Node parent = null;
Node cur = root;
while (cur != null)
{
parent = cur;
int r = key.compareTo(cur.key);
if (r == 0)
{
return cur.value;
}
else if (r < 0) {
cur = cur.left;
} else
{
cur = cur.right;
}
}
return null;
}
public V put(K key, V value){
if (root == null)
{ root = new Node<>();
root.key = key;
root.v
display(root);
return null;
}
Node parent = null;
Node cur = root;
while (cur != null)
{
parent = cur; int r = key.compareTo(cur.key);
if (r == 0)
{
V oldValue = cur.value;
cur.value = value;
display(root);
return oldValue;
}
else if (r < 0)
{
cur = cur.left;
}
else{
cur = cur.right;
}
}
Node node = new Node<>();
node.key = key;
node.value = value;
int r = key.compareTo(parent.key);
if (r < 0)
{ parent.left = node;
}
else { parent.right = node;
}
display(root);
return null;
}
public V remove(K key)
{ Node parent = null;
Node cur = root;
while (cur != null)
{
int r = key.compareTo(cur.key);
if (r == 0)
{
V oldValue = cur.value;
deleteNode(parent, cur);
display(root);
return oldValue; }
else if (r < 0)
{ parent = cur; cur = cur.left; }
else { parent = cur; cur = cur.right;
}
}
display(root);
return null;
}
private void deleteNode(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 {
// 去 cur 的右子树中寻找最小的 key 所在的结点 scapegoat
// 即 scapegoat.left == null 的结点
Node goatParent = cur;
Node scapegoat = cur.right;
while (scapegoat.left != null)
{ goatParent = scapegoat; scapegoat = cur.left; }
cur.key = scapegoat.key;
cur.value = scapegoat.value;
if (scapegoat == goatParent.left)
{
goatParent.left = scapegoat.right;
}
else { goatParent.right = scapegoat.right; }
}
}
private static ,V> void display(Node node)
{
System.out.print("前序: ");
preOrder(node); System.out.println();
System.out.print("中序: ")
inOrder(node);
System.out.println(); }
private static ,V> void preOrder(Node node)
{ if (node == null)
{ return; }
System.out.print(node + " ");
preOrder(node.left);
preOrder(node.right); }
private static ,V> void inOrder(Node node)
{ if (node == null)
{ return; }
inOrder(node.left);
System.out.print(node + " ");
inOrder(node.right); }
public static void main(String[] args)
{
BinarySearchTree tree = new BinarySearchTree<>();
int[] keys = { 5, 3, 7, 4, 2, 6, 1, 9, 8 };
for (int key : keys)
{
tree.put(key, String.valueOf(key)); }
System.out.println("=================================="); tree.put(3, "修改过的 3"); System.out.println("=================================="); tree.remove(9);
tree.remove(1); t
ree.remove(3);
``` }
} **六：性能分析**
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树。
**七： 和 java 类集的关系**
TreeMap 和 TreeSet 即 java 中利用搜索树实现的 Map 和 Set；另外有需要云服务器可以了解下创新互联cdcxhl.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。
