二叉查找树即搜索二叉树，或者二叉排序树（BSTree），学习回顾一下有关的知识。
>>关于二叉查找树
二叉查找树（Binary Search Tree）是指一棵空树或者具有下列性质的二叉树：
1. 若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若任意节点的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 任意节点的左、右子树也分别为二叉查找树。
4. 没有键值相等的节点，这个特征很重要，可以帮助理解二叉排序树的很多操作。
二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构。
>>基本性质
（1）二叉查找树是一个递归的数据结构，对二叉查找树进行中序遍历，可以得到一个递增的有序序列。
（2）二叉查找树上基本操作的执行时间和树的高度成正比。
对一棵n个节点的完全二叉树来说，树的高度为lgn，这些操作的最坏情况运行时间为O(lg n)，而如果是线性链表结构，这些操作的最坏运行时间是O(n)。
一棵随机构造的二叉查找树的期望高度为O(lg n)，但实际中并不能总是保证二叉查找树是随机构造的，
有些二叉查找树的变形能保证各种基本操作的最坏情况性能，比如红黑树的高度为O(lg n)，而B树对维护随机访问的二级存储器上的数据库特别有效。
注意对复杂度的理解，所谓的O(lg n)就是指复杂度是对数级别，是数量级的比较，和对数的底数其实没关系，
只要底数是大于1的，就是相同的数量级，有些书上说二叉查找树的复杂度是O(log2-n)，指的是相同的时间复杂度。
>>前驱和后继节点
一个节点的后继是该节点的后一个，即比该节点键值稍大的节点。
给定一个二叉查找树中的节点，找出在中序遍历顺序下某个节点的前驱和后继。
如果树中所有关键字都不相同，则某一节点x的前驱就是小于key[x]的所有关键字中最大的那个节点，后继即是大于key[x]中的所有关键字中最小的那个节点。根据二叉查找树的结构和性质，不用对关键字做任何比较，就可以找到某个节点的前驱和后继。
>>查找、插入与删除
（1）查找
利用二叉查找树左小右大的性质，可以很容易实现查找任意值和最大/小值。
在二叉查找树中查找一个给定的关键字k的过程与二分查找很类似，
首先是关键字k与树根的关键字进行比较，如果k比根的关键字大，则在根的右子树中查找，否则在根的左子树中查找，重复此过程，直到找到与遇到空节点为止。
在二叉查找树中查找x的过程如下：
1.若二叉树是空树，则查找失败。
2.若x等于根节点的数据，则查找成功，否则。
3.若x小于根节点的数据，则递归查找其左子树，否则。
4.递归查找其右子树。
（2）插入
二叉树查找树b插入操作x的过程如下：
1.若b是空树，则直接将插入的节点作为根节点插入。
2.x等于b的根节点的数据的值，则直接返回，否则。
3.若x小于b的根节点的数据的值，则将x要插入的节点的位置改变为b的左子树，否则。
4.将x要出入的节点的位置改变为b的右子树。
（3）删除
假设从二叉查找树中删除给定的结点z，分三种情况讨论：
1.节点z为叶子节点，没有孩子节点，那么直接删除z，修改父节点的指针即可。
2.节点z只有一个子节点或者子树，将节点z删除，根据二叉查找树的性质，将z的父节点与子节点关联就可以了。
3.节点Z有两个子节点，删除Z该怎样将Z的父结点与这两个孩子结点关联呢？
在删去节点Z之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整。
这种情况下可以用Z的后继节点来替代Z。
实现方法就是将后继从二叉树中删除，将后继的数据覆盖到Z中。
>>代码实现
主要参考《数据结构与算法分析—Java语言实现》：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 |
|