技術共有

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

二分探索ツリーの概念

二分探索木は、二分ソート木や二分探索木とも呼ばれ、二分木の一種で、次の 3 つの特徴があります。

1.二叉搜索树的左子树上的所有节点的val值均小于根节点的val值；
2.二叉搜索树的右子树上的所有节点的val值均大于根节点的val值；
3.二叉搜索树树的做右子树均为二叉搜索树。
1
2
3

簡単に言うと、このバイナリ ツリーのすべてのノードは、左の子 < 親ノード < 右の子を満たします。

二分探索木の演算

二分探索木探索

二分探索ツリーでの検索は、二分探索と似ています。検索がルート ノードより小さい場合は左側のサブツリーに進み、ルート ノードより大きい場合は右側のサブツリーに進みます。高さは最大回数まで検索できますが、空になっても見つからない場合は、値が存在しないことを意味します。

二分探索木の挿入

まず、検索方法に従い、ノードが空の場合に挿入します。これで二分探索木の挿入は完了です。

二分探索木の削除

二分探索木のノードの削除は、さまざまな状況に応じて実行する必要があります。

1.删除节点没有孩子，则可以直接删除。
2.删除节点有左孩子，被删除节点的父节点指向左孩子，然后直接删除该节点、
3.删除节点有右孩子，被删除节点的父节点指向右孩子，然后直接删除该节点。
4.删除节点有左右孩子，则找到右孩子中的最小值（中序遍历可以找到），用这个最小值取代该节点。
1
2
3
4