PS:这是我算法学习中的一点总结,有什么地方有错的欢迎大佬在评论区指出也欢迎学算法的朋友友与我一起讨论呀,如有侵权,请评论,我会第一时间联系版权方进行处理。(~ ̄▽ ̄)~

1.结构保证:左子树上的子孙节点必小于本节点,右子树上的子孙必大于本节点。

2.推论(功能实现的算法):

  1. 在搜索时,从根节点向下检索,每遇到一个节点,就比较本节点与被搜索数的大小。若节点数小于检索数则进入左子树,否则进入右子树,直至发现被搜索数或某一节点无子树或无应该进入的子树。
  2. 在插入时,从根节点向下检索,每遇到一个节点,就比较本节点与待插入数的大小。若节点数小于检索数则进入左子树,否则进入右子树,直至发现被搜索数或某一节点无子树或无应该进入的子树时就将待插入数插入到该节点合适的地方。
  3. 在删除时,从根节点向下检索,每遇到一个节点,就比较本节点与待删除数的大小。若节点数小于检索数则进入左子树,否则进入右子树,直至发现被搜索数,将其删除。删除后,判断。
    1. 若要删除的节点没有左儿子就将其右儿子提至该节点位置。
    2. 若要删除的节点的左儿子没有右儿子就将其左儿子提至该节点位置。
    3. 若不满足1.2.就将其左儿子的子孙中的最大节点提至该节点位置。

3.C++的STL实现。

可以使用C++STL里的set容器或map容器实现。

以下是常见用法的链接:

set容器的常见用法

map容器的常见用法

分类: ACM

0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注