二叉搜索树

二叉树的每个节点最多只能有2个子节点,分为左子节点和右子节点。

二叉搜索树:每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大。

二叉搜索树可以方便的实现搜索算法。在搜索元素x的时候,我们可以将x和根节点比较:
  • 1. 如果x等于根节点,那么找到x,停止搜索 (终止条件)
  • 2. 如果x小于根节点,那么搜索左子树
  • 3. 如果x大于根节点,那么搜索右子树

二叉搜索树所需要进行的操作次数最多与树的深度相等。n个节点的二叉搜索树的深度最多为n,最少为log2(n)+1。

二叉搜索树的操作:搜索,插入,删除,寻找最大最小节点。(每个节点中存有三个指针,一个指向父节点,一个指向左子节点,一个指向右子节点。

插入:
二叉搜索树的插入过程如下:
  • 1.若当前的二叉搜索树为空,则插入的元素为根节点。
  • 2.若插入的元素值小于根节点值,则插入到左子树中。
  • 3.若插入的元素值不小于根节点值,则插入到右子树中。

查找:



删除:
删除节点后,有时需要进行一定的调整,以恢复二叉搜索树的性质(每个节点都不比它左子树的任意元素小,而且不比它的右子树的任意元素大)。
  • 叶节点可以直接删除,并设置其双亲节点指针为空。
  • 若删除点只有左子树,或右子树,则设置其双亲节点的指针指向左子树或右子树。
  • 若删除点左右孩子均存在,则:
  • 1)查询删除点的右子树的左子树是否为空,若为空,则把删除点的左子树设为删除点的右子树的左子树。
  • 2)若不为空,则继续查询左子树,直到最底层的左子树为止。


```