기술나눔

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

이진 검색 트리 개념

이진 정렬 트리 또는 이진 검색 트리라고도 하는 이진 검색 트리는 다음과 같은 세 가지 특성을 가지고 있습니다.

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

간단히 말해서 이 이진 트리의 모든 노드는 왼쪽 자식 < 부모 노드 < 오른쪽 자식을 충족합니다.

이진 검색 트리 작업

이진 검색 트리 검색

이진 검색 트리의 검색은 이진 검색과 다소 유사합니다. 검색이 루트 노드보다 작으면 왼쪽 하위 트리로 이동하고, 루트 노드보다 크면 오른쪽 하위 트리로 이동합니다. 높이를 최대 횟수까지 검색할 수 있으며, 비어 있는 경우 해당 값이 존재하지 않는다는 의미입니다.

이진 검색 트리 삽입

먼저 검색 방법에 따라 노드가 비어 있을 때 삽입하면 이진 검색 트리 삽입이 완료됩니다.

이진 검색 트리 삭제

이진 검색 트리에서 노드를 삭제하는 작업은 상황에 따라 수행해야 합니다.

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